JJ has an array A initially of length N. He can perform the following operation on A:

1) Pick any index i (1 ≤ i ≤ |A|) such that A_{i} > 1 \
2) Select any two integers X and Y such that X + Y = A_{i} and X, Y ≥ 1 \
3) Replace A_{i} with X and Y

Note that the length of the array increases by 1 after each operation.

For example, if A = [4, 6, 7, 2], he can select i = 1 and select X = 1, Y = 3 (since X + Y = A_{1}). After the operation array becomes: $[\underline{4}, 6, 7, 2] \rightarrow [\underline{1}, \underline{3}, 6, 7, 2]$.

JJ wants to make A palindromic. Find the minimum number of operations to do so.

It is guaranteed that A can be converted to a palindromic array by using the above operation.

Note: An array is called a palindrome if it reads the same backwards and forwards, for e.g. [1, 3, 3, 1] and [6, 2, 6] are palindromic.

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

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N — the size of the array A.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$ denoting the array A.

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

For each test case, output the minimum number of operations to make A palindromic.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤A_{i} ≤10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
3
4
3 7 6 4
5
1 4 5 4 1
5
1 2 3 4 5

----- Sample Output 1 ------
2
0
4

----- explanation 1 ------
Test Case 1: We can perform the following operations:
- $[3, \underline{7}, 6, 4] \xrightarrow{i = 2, X = 1, Y = 6} [3, \underline{1}, \underline{6}, 6, 4]$
- $[3, 1, 6, 6, \underline{4}] \xrightarrow{i = 5, X = 1, Y = 3} [3, 1, 6, 6, \underline{1}, \underline{3}]$

Test Case 2: $A$ is already palindromic.

见题面

见题面