你和你的朋友 Pinky 有一个统治世界的计划。但首先，你们需要禁用某种秘密武器。

它隐藏在一个错综复杂的通道（图）中，该图只有一个入口。Pinky 将会到达存放秘密武器的顶点并将其禁用。与此同时，图入口处的安保团队会收到警报，并会穿过图试图及时赶到 Pinky 所在的位置阻止他。你将负责拖延安保团队，以便为 Pinky 争取尽可能多的时间。遍历图中的任何一条边需要 1 个单位时间，但你还可以额外“阻碍”最多 $K$ 个顶点。遍历一个被阻碍的顶点需要额外 1 个单位时间。你需要选择一组顶点进行阻碍，以使安保团队的行进时间尽可能长。

如果安保团队从图的入口出发，试图到达存放秘密武器的顶点，他们到达那里需要多少时间？ 请注意，你必须在安保人员开始旅程之前确定所有的阻碍点，安保人员会知道你阻碍了哪些顶点，并据此选择最优路径。

阻碍存放秘密武器的顶点是没有用的，因为在他们抓住 Pinky 之后，这并不会进一步延误安保人员。另一方面，阻碍入口显然是一个好主意。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含 $N$、$M$ 和 $K$。接下来的 $M$ 行，每行包含一对由边连接的顶点。顶点编号从 $0$（入口）到 $N - 1$（存放秘密武器的房间）。第一个顶点的编号总是小于第二个顶点，且同一测试用例中不会出现重复的顶点对。边是双向的——安保人员可以沿任一方向通过任何边。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是安保人员从入口到达存放秘密武器的房间所需的时间。

数据范围

$1 \le T \le 100$ $2 \le N \le 100$ $1 \le M \le N \times (N - 1) / 2$ $1 \le K \le N$ 从房间 $0$ 到房间 $N - 1$ 总存在一条路径。

样例

样例输入 1

5
3 2 1
0 1
1 2
3 2 2
0 1
1 2
3 2 3
0 1
1 2
4 4 2
0 1
0 2
1 3
2 3
7 11 3
0 1
0 2
0 3
1 4
1 5
2 4
2 5
3 4
3 5
4 6
5 6

样例输出 1

Case #1: 3
Case #2: 4
Case #3: 4
Case #4: 3
Case #5: 5