The NIT likes round screws. He also likes the operator because it reminds him of round screws, where represents Bitwise-XOR operation.
Define the value of a sequence as .
Given a sequence , you can perform the following operation for arbitrary times:
Select an index (), change to any non-negative integer; this operation has a cost .
Minimize the sum of the value of the sequence and the cost incurred by operations. In other words, let be the number of operations you performed, and be the value of the after the operations, then you need to minimize .
输入格式
The input contains multiple testcases. The first line of the input contains an integer (), the number of testcases.
For each testcase, the first line contains two integers (), the length of the sequence and the cost of performing an operation.
The second line contains integers (), representing the elements in the sequence.
It’s guaranteed that the sum of over all testcases does not exceed .
输出格式
For each testcase, print an integer in line, the minimum possible value of .
样例
样例输入 1
3
4 4
1 4 5 6
8 6
6 6 6 1 1 6 6 6
6 7
1 7 2 6 3 5
样例输出 1
14
24
29
数据范围与提示
For the st testcase, one way to achieve minimum is to change the sequence to ; the bold numbers are the changed. The final sequence value is , and operations are done; the total value cost is .
For the nd testcase, one way to achieve minimum is to change the sequence to ; the final value is .
