You are given with an array of n numbers. You must pick K elements from the array such that XOR of all the chosen elements is maximum.

See Bitwise XOR.

Input

The first line consists of an integer t representing the number of test cases. For each test case the first line consists of two numbers n and K denoting the number of elements in the array and the number of elements to be chosen respectively. Then in the next n lines, the elements in the array are given.

Output

For each test case print a line containing one integer denoting the maximum XOR value of the chosen K elements.

Constraints

Example

Input:
2
5 3
1
2
3
4
5
5 3
3
4
5
7
4

Output:
7
7