You are given an array $A$ of $n$ elements $A_1,A_2,A_3,\ ...,A_n$. Let us define a function $F(x)=\sum_{i=1}^{n} A_i \& x$.

Note: Here, $\&$ represents bitwise AND operator.

You are required to find the number of different values of $x$ for which $F(x)$ is maximized. There exists a condition for $x$ that it must have exactly $l$ bits sets in its binary representation.

Your task is to find a number of such values for which this function is maximized. Print the required number.

If there are infinite such numbers, then print -1.

It can be proved that under the given constraints the value to be printed is either infinite or not greater than 1e18.

Input format

• The first line contains the number of test cases, $T$.
• The second line contains two space-separated integers $n$ and $l$ (as described in the problem).
• The third line contains $n$ space seprated integers $A_1,A_2,A_3.....A_n$.

Output format

There are $T$lines of the output. The only line of output for each test case contains a single integer as described in the problem statement.

Constraints

$1\le T\le 1000$

$1\le l\le 30$

$1\le N\le 20000$

$1\le A[i]\le 1e9$

It is guaranteed that sum of $N$ over all test cases will not exceed 2e5.