You are given an array $A = [A_{1}, A_{2}, \ldots, A_{N}],$ consisting of N integers. In one move, you can take two adjacent numbers A_{i} and A_{i+1}, delete them, and then insert the number $A_{i} \land A_{i+1}$ at the deleted position. Here, $\land$ denotes [bitwise AND]. Note that after this operation, the length of the array decreases by one.

Formally, as long as |A| > 1 (where |A| denotes the current length of A), you can pick an index 1 ≤ i < |A| and transform $A into [A_{1}, A_{2}, \ldots, A_{i-1}, A_{i} \land A_{i+1}, A_{i+2}, \ldots, A_{|A|}]$.

Find the minimum number of moves required to make all numbers in the resulting array equal.

------ Input Format ------

• The first line of input contains an integer T — the number of test cases you need to solve.
• The first line of each test case contains one integer N, the size of the array.
• The second line of each test case contains $N space-separated integers A_{1}, \ldots, A_{N}$ — the elements of the array A.

------ Output Format ------

For each test case, output on a new line the minimum number of moves required to make all numbers equal.

------ Constraints ------

$1 ≤T ≤10^{6}$
$2 ≤N ≤10^{6}$
- Sum of $N$ over all test cases is at most $10^{6}$.
$0 ≤A_{i} < 2^{30}$

------ subtasks ------

Subtask 1 (20 points):
$0 ≤A_{i} ≤255$
Sum of $N$ over all test cases is at most $255$.
Subtask 2 (30 points):
Sum of $N$ over all test cases is at most $2000$.
Subtask 3 (50 points):
Original constraints.

----- Sample Input 1 ------
4
4
0 0 0 1
2
1 1
6
1 2 3 4 5 6
4
2 28 3 22

----- Sample Output 1 ------
1
0
4
3

----- explanation 1 ------
Test case $1$: Choose $i = 3$ to make the array $[0, 0, 0 \land 1] = [0, 0, 0]$.

Test case $2$: All elements of the array are already equal.

Test case $3$: One possible sequence of moves is as follows:
- Choose $i = 1$, making the array $[1\land 2, 3, 4, 5, 6] = [0, 3, 4, 5, 6]$
- Choose $i = 2$, making the array $[0, 0, 5, 6]$
- Choose $i = 3$, making the array $[0, 0, 4]$
- Choose $i = 2$, making the array $[0, 0]$

It can be verified that in this case, making every element equal using $3$ or fewer moves is impossible.

见题面

见题面