Maximum AND MAXAND18

Read problem statements in Hindi, Bengali, Mandarin Chinese, Russian, and Vietnamese as well.

Chef’s good friend Shubham has an assignment to complete, but he is too lazy to do it, so he asked Chef to help him. On the other hand, Chef was busy in the kitchen, so he in turn asked you to help Shubham.

You are given a sequence of positive integers $A_1, A_2, \ldots, A_N$ and an integer $K$. For any positive integer $X$ such that exactly $K$ bits in the binary representation of $X$ are equal to $1$, consider the sum $S = \sum_{i=1}^N (X \wedge A_i)$; here, $\wedge$ denotes bitwise AND. You should choose $X$ in such a way that $S$ is maximum possible. If there is more than one such value of $X$, you should find the smallest one.

Input

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first line of each test case contains two space-separated integers $N$ and $K$.
• The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

Output

For each test case, print a single line containing one integer ― the smallest possible value of $X$.

Constraints

• $1 \le T \le 1,000$
• $1 \le N \le 10^5$
• $1 \le K \le 30$
• $1 \le A_i \le 10^9$ for each valid $i$
• the sum of $N$ over all test cases does not exceed $10^5$

Subtasks

Subtask #1 (50 points): $K \le 2$

Subtask #2 (50 points): original constraints

Example Input

1
4 1
3 4 5 1

Example Output

4

Explanation

Example case 1: Exactly one bit in $X$ should be $1$. Our options are:

• If $X = 1$, $S = 1+0+1+1 = 3$.
• If $X = 2$, $S = 2+0+0+0 = 2$.
• If $X = 4$, $S = 0+4+4+0 = 8$.
• For any greater valid $X$, $S = 0$.

The maximum value of $S$ is $8$, so the answer is the only value of $X$ where we get $S = 8$.