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?
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$$$.
For each testcase, print the maximum possible sum of happiness.
13 31 1 1
0
15 31 2 3 4 5
10
