Background

愛してる過去の夜も　/　The nights of the past that I love.

今じゃ季節に煌めいてゆく　/　Now they also sparkle in time.

Problem Description

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 \lt 2^m$.

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

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

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

Yuki defines one "Bigger" operation as:

• Choose a positive integer $i$ with $i \le n$, and change $a_i$ to $(2 \cdot a_i) \bmod 2^m$.

Yuki wants to perform several "Bigger" operations (possibly $0$ times) to make the "Fish Value" of the sequence $a$ as large as possible.

You need to help her find the minimum number of "Bigger" operations needed to make the "Fish Value" of the sequence $a$ reach its maximum possible value.

Input Format

This problem has multiple test cases.

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

Then each test case is given as follows. For each test case:

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

Output Format

For each test case, output one line containing one integer, which is the minimum number of "Bigger" operations required to make the "Fish Value" of the sequence $a$ reach the maximum possible value.

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

5
0
8
3

Hint

Explanation of Sample 1

For the 1st test case, you can choose $i=1$ and perform the "Bigger" operation $3$ times, then choose $i=2$ and perform it $2$ times, making the sequence $a$ become $\{8,12,8\}$, and the "Fish Value" equals $8$. It can be proven that the maximum possible "Fish Value" of the sequence $a$ is $8$, and at least $5$ operations are required.

For the 2nd test case, no matter what operations you do, the "Fish Value" of the sequence $a$ is always $0$, so the answer is $0$.

Constraints

Let $\sum n$ denote the sum of $n$ within a single test point.

For all testdata, we have:

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

This problem uses bundled tests.

• 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 special constraints.

Translated by ChatGPT 5