Equalizer Ehrmantraut#12925

Equalizer Ehrmantraut

When Mike Ehrmantraut started being a cop, he wanted all people to be equal before the law. Now he is retired, but he still wants all elements of an integer array of length to become equal.

He can perform the following operations:

  1. Choose any such that 1 \leq i \leq n - 1 and set a_i = a_i \texttt{ AND } a_{i+1}.

  2. Choose any such that 2 \leq i \leq n and set a_i = a_i \texttt{ AND } a_{i-1}.

Find the smallest number of operations Mike needs to do to make all elements of equal.

Here AND denotes the bitwise AND operation.

Input

The first line contains a single integer (1 \leq t \leq 10^5) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer (2\leq n \leq 2\cdot 10^5)  — the length of the array.

The second line contains integers a_1, a_2, \ldots, a_n (0\leq a_i < 2^{30})  — the elements of the array.

It is guaranteed that the sum of over all test cases does not exceed 2\cdot 10^5.

Output

For each test case, output a single integer — the answer to the problem.

Examples

Example

Loading
Loading

Note

In the first test case, all numbers are already equal, so Mike doesn't need to do any operations.

In the second test case, it's enough to do the following operations:

  • Set a_2 equal to a_1 \texttt{ AND } a_{2} = 1 \texttt{ AND } 2 = 0.

  • Set a_1 equal to a_1 \texttt{ AND } a_{2} = 1 \texttt{ AND } 0 = 0.

  • Set a_3 equal to a_2 \texttt{ AND } a_{3} = 0 \texttt{ AND } 3 = 0.

  • Set a_4 equal to a_3 \texttt{ AND } a_{4} = 0 \texttt{ AND } 4 = 0.

  • Set a_5 equal to a_4 \texttt{ AND } a_{5} = 0 \texttt{ AND } 5 = 0.