P15867 [MX-X26-T3] "Cfz Round 7" GLACIES

愛してる過去の夜も　/　The nights of the past that I love. 今じゃ季節に煌めいてゆく　/　Now they also sparkle in time.

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.

**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$.

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.

### 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