Equal After And

 You are given an array 

A=[A1,A2,…,AN]$A=[A_1,A_2,\dots ,A_N]$, consisting of N$N$ integers. In one move, you can take two adjacent numbers Ai$A_i$ and Ai+1$A_{i+1}$, delete them, and then insert the number Ai∧Ai+1$A_i\wedge A_{i+1}$ at the deleted position. Here, ∧$\wedge$ denotes bitwise AND. Note that after this operation, the length of the array decreases by one.

Formally, as long as |A|>1$|A|>1$ (where |A|$|A|$ denotes the current length of A$A$), you can pick an index 1≤i<|A|$1\le i<|A|$ and transform A$A$ into [A1,A2,…,Ai−1,Ai∧Ai+1,Ai+2,…,A|A|]$[A_1,A_2,\dots ,A_{i-1},A_i\wedge A_{i+1},A_{i+2},\dots ,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$T$ — the number of test cases you need to solve.
• The first line of each test case contains one integer N$N$, the size of the array.
• The second line of each test case contains N$N$ space-separated integers A1,…,AN$A_1,\dots ,A_N$ — the elements of the array A$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≤106$1\le T\le {10}^6$
• 2≤N≤106$2\le N\le {10}^6$
• Sum of N$N$ over all test cases is at most 106${10}^6$.
• 0≤Ai<230$0\le A_i<2^{30}$

Subtasks

• Subtask 1 (20 points):
  • 0≤Ai≤255$0\le A_i\le 255$
  • Sum of N$N$ over all test cases is at most 255$255$.
• Subtask 2 (30 points):
  • Sum of N$N$ over all test cases is at most 2000$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

Test case 1$1$: Choose i=3$i=3$ to make the array [0,0,0∧1]=[0,0,0]$[0,0,0\wedge 1]=[0,0,0]$.

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

Test case 3$3$: One possible sequence of moves is as follows:

• Choose i=1$i=1$, making the array [1∧2,3,4,5,6]=[0,3,4,5,6]$[1\wedge 2,3,4,5,6]=[0,3,4,5,6]$
• Choose i=2$i=2$, making the array [0,0,5,6]$[0,0,5,6]$
• Choose i=3$i=3$, making the array [0,0,4]$[0,0,4]$
• Choose i=2$i=2$, making the array [0,0]$[0,0]$

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