Aliens have landed on earth, and you, who are studying OI, have received a problem about aliens.

You are given an array $a$ of $n$ positive integers numbered from $1$ to $n$, and a number $m$.

The value of a substring is the bitwise-OR of all its elements, minus $m$.

You want to divide the sequence into some substrings and minimize the sum of their values.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1\le T\le 10^5$) --- the number of test cases. Description of the test cases is as follows.

The first line of each test case contains two integers $n$ and $m$ ($1\le n\le 10^5$, $0\le m\le 10^9$).

The second line of each test case contains the $n$ integers of the array $a_1,a_2,\cdots,a_n$ ($0\le a_i\le 10^9$).

It is guaranteed that the sum of $n$ over all test cases is not greater that $5\times 10^5$.

Output

For each test case, print a single line with the minimum sum of values.

Example

Input

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

Output

5
0
148
-99

Explanation

• An optimal way in first case: $\{5,1,3,2,4\}$.
• An optimal way in second case: $\{5\},\{1\},\{3\},\{2\},\{4\}$.
• An optimal way in third case: $\{128\},\{31,30,28\},\{64\}$.
• An optimal way in fourth case: $\{1\}$.

Notice that the answer could be negative.

Subtasks

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

Subtask 2 (19 pts): $\sum n\leq 10^2$

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

Subtask 4 (40 pts): No special restrictions

For $100\%$ data, it's guaranteed $1\le n,T\le 10^5$, $\sum n\leq 5\times 10^5$, $0\leq a_i,m\le 10^9$.