E. Sequence
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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
Note

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$$$.

  • 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.