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.