2.4 Making a Palindromic Array

Score: 15pts

Time Limit: 5.00 sec

JJ has an array A of length N initially. He has a special operation available, which allows him to modify the array as follows:

1. Choose an index i (1 ≤ i ≤ |A|) such that Ai > 1.

2. Select two integers X and Y (X + Y = Ai) with X, Y ≥ 1.

3. Replace Ai with X and Y.

Note that after each operation, the length of the array increases by 1. JJ's goal is to make the array A palindromic, i.e., an array that reads the same forwards and backwards. Find the minimum number of operations required to achieve this goal.

It is guaranteed that A can be converted into a palindromic array using the given operation.

1. Choose an index i (1 ≤ i ≤ |A|) such that Ai > 1.

2. Select two integers X and Y (X + Y = Ai) with X, Y ≥ 1.

3. Replace Ai with X and Y.

Note that after each operation, the length of the array increases by 1. JJ's goal is to make the array A palindromic, i.e., an array that reads the same forwards and backwards. Find the minimum number of operations required to achieve this goal.

It is guaranteed that A can be converted into a palindromic array using the given operation.

Constraints

1≤T≤105

1≤N≤10^5

1≤Ai≤10^5

Sum of N over all test cases does not exceed 2⋅10^5

1≤N≤10^5

1≤Ai≤10^5

Sum of N over all test cases does not exceed 2⋅10^5

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 A1,A2,…,AN denoting the array A.

-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 A1,A2,…,AN denoting the array A.

Output Format

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

Example 1

Input:

3

4

3 7 6 4

5

1 4 5 4 1

5

1 2 3 4 5

Output:

2

0

4

Explanation:

Test Case 1: We can perform the following operations:

[3,7,6,4]

lets i=2,X=1,Y=6,

so transforms to [3,1,6,6,4]

[3,1,6,6,4]

lets i=5,X=1,Y=3

[3,1,6,6,1,3]

so ans is 2.

Test Case 2: A is already palindromic

so ans is 0

3

4

3 7 6 4

5

1 4 5 4 1

5

1 2 3 4 5

Output:

2

0

4

Explanation:

Test Case 1: We can perform the following operations:

[3,7,6,4]

lets i=2,X=1,Y=6,

so transforms to [3,1,6,6,4]

[3,1,6,6,4]

lets i=5,X=1,Y=3

[3,1,6,6,1,3]

so ans is 2.

Test Case 2: A is already palindromic

so ans is 0