Jehta a famous INTER-NIT player at delhi meets a girl and proposes her but she if so fond of mathematics that she doesn't wanna break with her BF as he is a top notch mathematician (We can not disclose). So to have better mathematician as her BF she challenges manish aka jetha and was 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$

Here & represents BIT WISE AND operator.

He needs to find the number of different values of  x  for which $F(x)$ is maximized.

But there is a constraint for x that it must have exactly l bits-set in its binary representation.

Being a good mathematician(Self-Declared) he calculated the answer just to verify wants you to do as well.

Vacancies are still open as she found that both had back-logs in the semester exams(Problem setter has good chances :) ).

Your task is to find number of such values for which this function is maximised.

Print the required number.

If there are infinite  such numbers output -1.

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

Video approach to solve this question: here

Input:

First line will contain number of test cases T.

Second line of input will contain two space seprated integers n and l (As described in the problem).

Third and final line of input contains n space seprated integers $A_1,A_2,A_3.....A_n$.

Output:

There will be T lines of output:

The only line of output for each test case  contains a single integer as described in problem.

Constraints:

$1<=T<=1000$

$1<=l<=30$

$1<=N<=20000$

$1<=A[i]<=1e9$

As promised he is a good mathematician but no one wants too much burden so it is guaranteed that sum of $N$ over all test cases will not exceed 2e5.