都市国久违的庆典就要到了，其中一项很重要的活动就是收集力量之月。已知都市国一共有 $n$ 栋建筑藏有力量之月，这些建筑从 $1$ 到 $n$ 标号。这些建筑之间用 $m$ 条双向道路连接了起来，每条道路的长度都为 $1$，任意两栋建筑之间都可以互相到达。由于市长宝琳觉得那些自己和自己相连的建筑非常有趣，所以连接同一栋建筑的道路是可能存在的。
但是，现在都市国的交通还不是太方便，有些建筑之间要走很远才能到达。因此宝琳想要新修建一些道路，直到满足下面的要求：如果两栋建筑（可以相同）之间有一条长度为 $k$ 的路径（不必都是输入的 $m$ 条边，也不必是简单路径），那么它们之间要有一条双向道路直接相连。当然修路的花费是很高的，宝琳希望修最少的路以满足要求。那么，最少需要修建多少条路呢？
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
第一行包含三个整数 $n$，$m$ 和 $k$，含义见题目描述。
接下来 $m$ 行，第 $i$ 行包含两个整数 $u_{i}$ 和 $v_{i}$，表示建筑 $u_{i}$ 和 $v_{i}$ 间有一条双向道路连接。
保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。
保证所有的数据满足 $1\le T\le 5\cdot10^{5}$。
保证所有的数据满足 $1\le n,k\le 2\cdot10^{5}$，$0\le m\le 2\cdot10^{5}$，所有数据的 $\sum n,\sum m\le 2\cdot10^{6}$。
保证所有的数据满足 $1\le u_{i},v_{i}\le n$，任意两栋建筑可以互相到达。
保证所有的数据满足 $i\neq j$ 时，$(u_{i},v_{i})\neq(u_{j},v_{j})$ 且 $(u_{i},v_{i})\neq(v_{j},u_{j})$。
对于每组数据，输出一行，格式为 Case #number: result，其中 $\mathrm{number}$ 表示这是第 $\mathrm{number}$ 组数据，而 $\mathrm{result}$ 为该组数据的答案。
1
3 2 2
1 2
2 3Case #1: 4