在三国时期，吴国有一位名叫陆逊的将军。有一次，他的部队在追击刘备时，被诸葛亮困在了八卦阵中。这个谜题可以看作是一个包含 $N$ 个顶点和 $M$ 条边的无向图。谜题中的每条边连接两个顶点 $u_i$ 和 $v_i$，长度为 $w_i$。诸葛亮对他的谜题设计非常感兴趣，因此图中没有自环，且任意两个顶点之间最多只有一条边。此外，保证图中任意两个顶点之间至少存在一条路径。

幸运的是，有一位名叫黄承彦的老人愿意帮助陆逊破解这个谜题。黄承彦告诉陆逊，他必须选择一个顶点作为起点，走过一些边，最后回到起点。在行走过程中，他可以多次经过某些边。由于诸葛亮拥有某种神秘的魔法，陆逊只有在找到一条路径，使得他所经过的所有边的长度的异或和最大时，才能破解这个谜题。如果他多次经过某条边，该边的长度也会被计算多次。现在，你能告诉陆逊这个谜题中最大的异或回路路径是多少，以帮助他破解谜题吗？

输入格式

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

每个测试用例的第一行包含两个整数 $N(2 \le N \le 5 \times 10^4)$ 和 $M(1 \le M \le 10^5)$。接下来的 $M$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i(1 \le u_i, v_i \le N, 0 \le w_i \le 2^{60} - 1)$，用于描述谜题中的所有边。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是谜题中某条回路路径的最大异或和。

样例

样例输入 1

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

样例输出 1

Case #1: 3
Case #2: 3

说明

异或（XOR）运算是对两个等长的位模式进行逻辑异或操作。如果两个对应位中只有一个为 1，则结果位为 1；如果两个位都为 0 或都为 1，则结果位为 0。即比较两个位，若不同则为 1，相同则为 0。