你正在玩一个游戏，战场由 $N$ 个城市和 $R$ 条双向道路组成。你的目标是从你选择的某个城市 $C$ 出发，恰好经过所有 $R$ 条道路一次，并最终在 $C$ 结束旅程。如果这是不可能的，你必须在初始道路集合中添加最少数量的额外道路，以使这次旅程可行。请注意，同一对城市之间可能有多条道路连接，并且无论它们之间是否已经有道路连接，你都可以在任意一对城市之间添加道路，如样例输入/输出所示。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。对于每个测试用例，包含以下内容：

• 一行包含一个整数 $N$，表示城市的数量。
• 一行包含一个整数 $R$，表示道路的数量。
• $R$ 行对应这些道路。每行包含两个由空格隔开的整数 $A$ 和 $B$。$A$ 和 $B$ 是两个不同的整数（$0 \le A, B < N$），表示该道路的两个端点。

数据范围

• $1 \le T \le 30$
• $2 \le N \le 1000$

子任务（12 分）

• $1 \le R \le 15$

子任务（21 分）

• $1 \le R \le 10^4$

输出格式

对于每个测试用例，输出一行，包含 Case #x:，其中 $x$ 是测试用例的编号，后跟所需的最少道路数量。

样例

输入样例 1

3
2
2
0 1
0 1
3
3
1 2
1 2
2 1
4
5
0 1
2 0
0 3
1 2
3 1

输出样例 1

Case #1: 0
Case #2: 1
Case #3: 1