+ Time Limit: 1 second
+ Memory Limit: 256 MB
----------
You are given an array of length $n \geq 2$ like $a_1, a_2, \dots, a_n\,\,$. You may perform each of the following operations any number of times:
* Choose an index $i$ $(1 \leq i \leq n - 1)$ and replace $a_i$ with $\lfloor\dfrac{a_i + a_{i+1}}{2}\rfloor\,$.
* Choose an index $i$ $(2 \leq i \leq n)$ and replace $a_i$ with $\lfloor\dfrac{a_{i-1} + a_i}{2}\rfloor\,$.
Your task is to determine, for each test case, the minimum number of operations required to maximize the sum of the array.
# Input
The first line contains an integer $t$, the number of test cases.
$$1 \le t \le 10^4$$
The first line of each test contains an integer $n$, the length of the array.
$$2 \leq n \le 2 \times 10^5$$
The second line contains $n$ integers $a_1, a_2, \dots, a_n\,\,$, the elements of the array.
$$1 \leq a_i \leq 10^9$$
It is guaranteed that $\sum n$ over all test cases does not exceed $2 \times 10^5$.
# Output
For each test case print a single integer, the minimum number of operations required to maximize the total sum of the array.
# Examples
### Sample Input 1
```
4
2
1 3
5
9 3 4 8 2
3
5 1 7
2
1000 1000
```
### Sample Output 1
```
1
8
3
0
```