Mister IP went to the Carpathian Mountains to celebrate his birthday and brought home a souvenir from there — a constructor resembling the shape of a mountain.
However, while carrying it home, some pieces got lost, so now the constructor consists of segments, with the -th segment having a height of a_i. Mister IP wants to make it look like a mountain again to keep the memories of his birthday!
He thinks that a constructor consisting of segments of heights b_1, b_2, \dots, b_n looks like a mountain if there exists at least one index (1 \le m \le n) such that for each 1 \le i < m, b_{i} \le b_{i+1}, and for each m < i \le n, b_{i-1} \ge b_{i}.
To make his constructor look like a mountain, he may do the following action any number of times:
pick any segment ,
pick a positive integer (0 < x < 2^{30}), and for a cost of coins, change segment's height a_j := a_j \mid x (the explanation of the symbol is available at the bottom of the page).
Mister IP doesn't have too many coins, so now he wonders what is the smallest number of coins he needs to be able to make his constructor look like a mountain again. Help him find this number!
The first line of input contains an integer (1 \le t \le 5 \cdot 10^4) — the number of test cases. Each test case must be solved independently.
The first line of each test case contains the integer (3 \le n \le 2 \cdot 10^5) — the number of segments in the constructor.
The second line of each test case contains integers a_1, a_2, \dots, a_n (1 \le a_i < 2^{30}) — the heights of the segments.
It is guaranteed that the sum of values of across all test cases does not exceed 2 \cdot 10^5.
For each test case output a single integer — the smallest number of coins needed to make Mister IP's constructor look like a mountain.
Example 1
The symbol stands for the "bitwise OR" operator.
Bitwise OR of two numbers and works as follows:
Consider the binary representation of p = \overline{(p_0 p_1 \dots p_{29})}_2 and q = \overline{(q_0 q_1 \dots q_{29})}_2, where p_i, q_i \in \{0, 1\}, and p = \sum_{i=0}^{29} p_i \cdot 2^i and q = \sum_{i=0}^{29} q_i \cdot 2^i respectively. It can be shown that such representations are unique for each number.
The result of the operation r = \overline{(r_0 r_1 \dots r_{29})}_2 = \sum_{i=0}^{29} r_i \cdot 2^{i} is calculated as follows:
r_i = p_i\ \textbf{or}\ q_i, where is defined as follows:
First Bit | Second Bit | Result Bit |
For example,
if p = 5 = \overline{(1010)}_2 and q = 12 = \overline{(0011)}_2, then p \mid q = \overline{(1011)}_2 = 13;
if p = 6 = \overline{(011)}_2 and q = 7 = \overline{(111)}_2, then p \mid q = \overline{(111)}_2 = 7.
In the first test case, Mister IP can perform the operation twice:
pick segment , and for a cost of coins, make a_3 := 3 \mid 4 = 7.
pick segment , and for a cost of coin, make a_5 := 2 \mid 1 = 3.
After these, the constructor looks as follows: [2, 5, 7, 8, 3, 3] with index m = 4 satisfying a_1 \le a_2 \le a_3 \le a_4 \ge a_5 \ge a_6. The total cost is 4+1 = 5. It can be shown that it's impossible to achieve the goal with a smaller cost.
In the second test case, Mister IP can perform the operation once on segment , paying coins to make a_2 := 1 \mid 2 = 3. No operation with cost can make the array look like a mountain; hence this is the smallest answer.
In the third case, the segment with index m = 5 already satisfies the property a_1 \le a_2 \le a_3 \le a_4 \le a_5, hence applying no operations is needed.
( points): n \le 5, a_i \le 15
( points): a_i \le 2
( points): a_i \le 63
( points): n \le 100
( points): no additional restrictions.