A. Submission Bait
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a sequence $$$a$$$ containing $$$n$$$ positive integers.

In one operation, you can split an element into two adjacent positive elements. The other parts of the sequence remain unchanged.

For example: $$$a=[3,2,1]$$$, if you split $$$a_1=3$$$ into $$$1$$$ and $$$2$$$, you'll get $$$a=[1,2,2,1]$$$.

Find the minimum nunber of operations to turn $$$a$$$ into a palindrome sequence. It can be proven that you can always do it.

A palindrome sequence is a sequence that reads the same backwards as forwards.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2\le n \le 3 \cdot 10^{5}$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The sum of $$$n$$$ over all test cases will not exceed $$$3 \cdot 10^{5}$$$.

Output

For each test case, output a single integer — the minimum number of operations to turn $$$a$$$ into a palindrome sequence.

Example
Input
4
3
3 2 1
2
1 1
6
6 5 4 3 2 1
8
8 7 7 1 9 4 2 2
Output
1
0
3
5
Note

In the first test case, we use the following scheme: $$$[\underline{3},2,1]\xrightarrow{}[1,2,2,1]$$$.

In the second test case, we don't need to do anything.

In the third test case, we use the following scheme:$$$[\underline{6},5,4,3,2,1]\xrightarrow{}[1,\underline{5},5,4,3,2,1] \xrightarrow{}[1,2,3,\underline{5},4,3,2,1] \xrightarrow{}[1,2,3,4,1,4,3,2,1]$$$.