愛してる過去の夜も / Even the nights of the past that I loved 今じゃ季節に煌めいてゆく / Are now shining in the seasons

Yuki has a sequence $a$ of length $n$ and a positive integer $m$. It is guaranteed that for all $1 \le i \le n$, $0 \le a_i < 2^m$.

For the sequence $a$, Yuki defines its "Fishy Value" as:

$$ a_1 \text{ and } a_2 \text{ and } \cdots \text{ and } a_n $$

That is, the result of the bitwise AND of all numbers in the sequence $a$.

Yuki defines a "Big" operation as follows:

• Choose a positive integer $i \le n$ and update the value of $a_i$ to $(2 \cdot a_i) \bmod 2^m$.

Yuki wants to perform some number of "Big" operations (possibly zero) such that the "Fishy Value" of the sequence $a$ is maximized.

You need to help her find the minimum number of "Big" operations required to make the "Fishy Value" of the sequence $a$ reach its maximum possible value.

Input

The first line contains two integers $c$ and $t$, representing the subtask ID and the number of test cases, respectively. The sample satisfies $c=0$.

Each test case is then provided as follows:

• The first line contains two integers $n$ and $m$.
• The second line contains $n$ integers $a_1, \dots, a_n$.

Output

For each test case, output a single line containing an integer representing the minimum number of "Big" operations required to make the "Fishy Value" of the sequence $a$ reach its maximum possible value.

Examples

Input 1

0 4
3 4
1 3 8
2 3
4 0
3 5
3 6 11
3 4
5 7 13

Output 1

5
0
8
3

Note 1

For the first test case, one can choose $i=1$ and perform $3$ "Big" operations, then choose $i=2$ and perform $2$ "Big" operations, transforming the sequence $a$ into $\{8, 12, 8\}$. The "Fishy Value" becomes $8$. It can be proven that the maximum possible "Fishy Value" for sequence $a$ is $8$, and at least $5$ operations are required.

For the second test case, no matter what operations are performed, the "Fishy Value" of the sequence $a$ will always be $0$, so the answer is $0$.

Constraints

Let $\sum n$ denote the sum of $n$ in a single test case.

For all test cases:

• $1 \le t \le 5\cdot 10^5$;
• $1 \le n \le 5\cdot 10^5$, $1 \le m \le 60$, $\sum n \le 5\cdot 10^5$;
• For all $1 \le i \le n$, $0 \le a_i < 2^m$.

This problem uses bundled testing.

• Subtask 1 (15 points): $n, m \le 8$, $\sum n \le 8$.
• Subtask 2 (18 points): $n \le 10^3$, $m \le 10$, $\sum n \le 10^3$.
• Subtask 3 (21 points): $n \le 10^4$, $m \le 20$, $\sum n \le 10^4$.
• Subtask 4 (21 points): $n \le 10^5$, $m \le 30$, $\sum n \le 10^5$.
• Subtask 5 (25 points): No additional constraints.