D. Could you help the judges?
time limit per test
1 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

On June-22-2023, Al-Baath University is supposed to hold a local contest, but the judges are still uncertain whether the problemset is easy or difficult.

The contest consists of $$$n$$$ problems, each with a value $$$a_i$$$.

One of the judges, $$$\textit{YouStill-DontKnowMeYet}$$$, suggests determining the difficulty of the contest by taking the $$$XOR$$$ value of some of the problems values and finding the largest $$$XOR$$$ value.

However, another judge, $$$\textit{Blade-Master}$$$, argues that determining the contest's difficulty is more challenging than the most challenging problem in the contest. They suggest focusing only on a range of problems from $$$l$$$ to $$$r$$$ and finding the $$$XOR$$$ value of those problems.

Later on, the judges realize that the contest is too easy, so they decide to add a problem with $$$k$$$ tags to make it more challenging.

The number of tags for a problem refers to the number of ones in its binary representation.

Given the current set of problems and the value of $$$k$$$, your task is to help the judges and determine the $$$maximum$$$ difficulty that can be achieved by adding a problem that satisfies the given conditions.

In other words, You are given an array $$$a$$$ of length $$$n$$$, you have to insert an integer $$$x$$$ $$$(0 \le x \le 1023)$$$ to the array $$$a$$$ in any position you want so the array becomes in length $$$n+1$$$.

the number $$$x$$$ should have exactly $$$k$$$ ones in the binary representation.

Your task is to find $$$\max\limits_{1 \le l \le r \le n + 1}(a_l\oplus a_{l+1} \oplus \dots \oplus a_r)$$$

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10)$$$ — the number of test cases.

The first line of each test case contains two integers $$$n,k$$$ $$$(1 \le n \le 10^5 , 0 \le k \le 10)$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ $$$(0 \le a_i \le 1023)$$$

Output

For each test case, output one integer: The maximum difficulty that can be achieved by adding a problem that satisfies the given conditions.

Example
Input
3
5 2
8 5 256 128 37
4 2
256 512 256 128
3 2
3 56 640
Output
1000
992
1019
Note

in the first test case we insert the element x = 576 in any position and take the XOR of all elements in the resulting array so the answer will be 1000. in the third test case we insert the element x = 320 in any position and take the XOR of all elements in the resulting array so the answer will be 1019.