You are given a permutation $p = (p_1, p_2, \dots, p_n)$ of the integers from $1$ to $n$.

In one operation, you may choose an index $i$ ($1 \le i \le n - 2$) such that

and swap $p_i$ with $p_{i+2}$ (leaving $p_{i+1}$ in place).

Determine whether it is possible to sort $p$ in ascending order — that is, obtain $p = (1, 2, \dots, n)$ — using any number of operations (possibly zero). If it is possible, find the minimum number of operations required.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^6$) --- the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$) --- the length of the permutation.

The second line of each test case contains $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) --- the elements of the permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer: the minimum number of operations required to sort the permutation in ascending order, or -1 if it is impossible.

Example

stdin

3
5
3 2 1 4 5
4
2 1 4 3
5
5 4 3 2 1

stdout

1
-1
-1

Note

In the first test case, we can choose $i = 1$ since $p_1 > p_2 > p_3$ ($3 > 2 > 1$). Swapping $p_1$ and $p_3$ transforms the permutation into $(1, 2, 3, 4, 5)$, which is sorted in ascending order using $1$ operation.

In the second test case, there is no index $i$ ($1 \le i \le 2$) satisfying $p_i > p_{i+1} > p_{i+2}$. Since no operation can be performed and the permutation is not sorted, the answer is \texttt{-1}.

In the third test case, although valid operations exist initially (for instance, choosing $i = 1$ yields $(3, 4, 5, 2, 1)$), it can be proven that no sequence of operations can transform $(5, 4, 3, 2, 1)$ into $(1, 2, 3, 4, 5)$. Thus, the answer is -1.