给定一个包含 $N$ 个顶点和 $M$ 条边的简单图。简单图是指没有自环（连接同一个顶点的两条边）且任意两个不同顶点之间最多只有一条边的无向图。初始时，每条边都被染成白色。每一轮你可以选择一条白色边并将其染成红色。你不能生成仅由红色边组成的奇数长度环。请问最多可以将多少条边染成红色？

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 30$)。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含两个整数 $N$ 和 $M$ ($2 \le N \le 16$, $1 \le M \le N(N - 1)/2$)。

接下来的 $M$ 行中，第 $i$ 行描述第 $i$ 条边：两个整数 $u, v$ 表示 $u$ 和 $v$ 之间的一条边。保证图中没有自环和重边。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是可以染成红色的边的最大数量。

样例

样例输入 1

2
4 5
1 2
1 3
1 4
2 4
3 4
5 6
1 2
2 3
3 1
1 4
4 5
3 5

样例输出 1

Case #1: 4
Case #2: 5