外星人登陆了地球，正在学习 OI 的你接收到了外星人的题目。

给定一个长度为 $n$ 的非负整数序列 $a$ 和一个常数 $m$，元素从 $1$ 到 $n$ 编号。

你需要将其划分成若干非空子串。

对于每个非空子串，其价值为所有元素按位或的结果减去常数 $m$。

输出所有划分方法中所有子串价值和的最小值。

输入格式

本题有多组测试数据。

第一行输入一个整数 $T$，代表测试组数，接下来输入 $T$ 组数据。

对于每组数据输入两行，第一行输入两个整数 $n,m$，第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

对于每组数据输出一行，包含一个整数，代表你的答案。

样例数据

样例输入

4
5 2
5 1 3 2 4
5 3
5 1 3 2 4
5 25
128 31 30 28 64
1 100
1

样例输出

5
0
148
-99

样例解释

对于第一组数据，一种最优的划分方案为 $\{5,1,3,2,4\}$。

对于第二组数据，一种最优的划分方案为 $\{5\},\{1\},\{3\},\{2\},\{4\}$。

对于第三组数据，一种最优的划分方案为 $\{128\},\{31,30,28\},\{64\}$。

对于第四组数据，一种最优的划分方案为 $\{1\}$，注意答案不一定是非负整数。

子任务

本题采用捆绑测试。

Subtask 1 (13 pts) ：$m=0$

Subtask 2 (19 pts) ：$\sum n\leq10^2$

Subtask 3 (28 pts) ：$\sum n\leq 10^3$

Subtask 4 (40 pts) ：无特殊限制

对于 $100\%$ 的数据，保证 $1\le n,T\le 10^5$，$\sum n\leq 5\times 10^5$，$0\leq a_i,m\le 10^9$。