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.