K. 3awdat al3lakat
time limit per test
2 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

If you know Obada, then you know how much he loves his friends. Obada was not happy because of all the problems between Ammar and Ahmad and decided to invite them to a party and solve all the problems so they become friends again. Obada invited $$$k$$$ people in total.

Obada and his friends are programmers, and programmers don't eat cake at parties; they eat arrays. Obada made a delicious array $$$a$$$ of $$$n$$$ integers. He wants to divide it into exactly $$$k$$$ non-empty subarrays such that each element of $$$a$$$ is in exactly one subarray , and give each subarray to one of his friends. Obada wants the friends to be happy, so he wants to maximize the sum of happiness of the friends. If a friend got the subarray $$$L,R$$$, then his happiness will be equal to the maximum $$$a[w] \oplus a[x] \oplus a[y] \oplus a[z]$$$ over all $$$(L \leq w, x, y, z \leq R)$$$, where $$$\oplus$$$ is the xor binary operation. Note that $$$w,x,y,z$$$ don't have to be distinct.

Can you help Obada find the maximum possible sum of happiness?

Input

The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$— the number of testcases.

The first line of each testcase consists of two integers $$$n,k \: (1 \leq k \leq n \leq 500)$$$ —the size of the array and the number of friends.

The second line of each testcase contains $$$n$$$ integers $$$a_i \: (0 \leq a_i \leq 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$500$$$.

Output

For each testcase, print the maximum possible sum of happiness.

Examples
Input
1
3 3
1 1 1
Output
0
Input
1
5 3
1 2 3 4 5
Output
10