Description

Input

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Descriptions of test cases follow.

The first line of each test case contains an integer $n$ ($1\le n \le 10^5$) — size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — elements of the array.

It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case output the number $k$, the minimal number of operations you need to sort the array. If it is impossible to sort the array using these operations, output $-1$.

11
5
3 2 1 5 4
5
1 1 2 1 1
4
3 7 10 5
5
1 2 3 4 5
2
5 1
3
3 4 1
5
4 1 3 4 4
3
5 1 1
4
2 5 5 4
5
2 2 1 1 2
2
5 5
 
 
 
 
 
 
 
 
 
 
 
 

3
2
-1
0
1
1
3
1
2
2
0

Note

In the first test case of the example, to sort the array [$3, 2, 1, 5, 4$] you need to perform $3$ operations:

• Shift to obtain the array [$4, 3, 2, 1, 5$];
• Shift to obtain the array [$5, 4, 3, 2, 1$];
• Reverse to obtain the array [$1, 2, 3, 4, 5$].

In the third test case of the example, it can be shown that it is impossible to sort the array using the given operations.

In the seventh test case of the example, to sort the array [$4, 1, 3, 4, 4$] you need to perform $3$ operations:

• Reverse to obtain the array [$4, 4, 3, 1, 4$];
• Shift to obtain the array [$4, 4, 4, 3, 1$];
• Reverse to obtain the array [$1, 3, 4, 4, 4$].