黄焖鸡是一道广受欢迎的中国菜，以其浓郁的口味和香气而闻名。它起源于山东省，在中国乃至海外都广受欢迎。这道菜主要由鸡肉配以咸甜适口的酱汁焖制而成，并辅以蘑菇、青椒和竹笋等各种蔬菜。

图 3：黄焖鸡米饭。CC-BY-SA-4.0

Little Cyan Fish 最近发现了一个名为“门吉之战”（Battle of Menjis）的游戏。现在，Alice 和 Bob 正在玩这个游戏。

游戏开始时有一个包含 $n$ 个非负整数的序列 $a_1, \dots, a_n$。Alice 和 Bob 轮流进行操作，Alice 先手。

在 Alice 的回合，她可以选择一个下标 $i$ ($1 \le i \le n$)，并将 $a_i$ 替换为 $a_i + 1$。

在 Bob 的回合，他可以选择一个满足 $a_i > 0$ 的下标 $i$ ($1 \le i \le n$)（可以证明这样的 $i$ 一定存在），并将 $a_i$ 替换为 $a_i - 1$。

当 Alice 和 Bob 各自进行了 $k$ 次操作后，游戏结束。

Alice 希望最大化 $\bigoplus_{i=1}^n a_i$，而 Bob 希望最小化 $\bigoplus_{i=1}^n a_i$。其中 $\bigoplus_{i=1}^n a_i$ 表示序列 $a$ 的按位异或和。

可以证明，对于两名玩家，最优策略均存在。请确定当两名玩家采取最优策略时，最终的 $\bigoplus_{i=1}^n a_i$ 的值。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, k$ ($1 \le n \le 10^5, 1 \le k \le 10^9$)，第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$)。

保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示两名玩家采取最优策略时最终的 $\bigoplus_{i=1}^n a_i$。

样例

输入 1

4
2 3
1 1
4 4
0 0 0 0
4 1
1 2 4 8
13 5
1 1 4 5 1 4 1 9 1 9 8 1 0

输出 1

0
0
9
11