You are given a positive integer N and an array A of size N. There are $N lists L_{1}, L_{2} \ldots L_{N}. Initially, L_{i} = [A_{i}]$.

You can perform the following operation any number of times as long as there are at least 2 lists:

Select 2 (non-empty) lists L_{i} and $L_{j} (i \neq j)$
Append L_{j} to L_{i} and remove the list L_{j}. Note that this means L_{j} cannot be chosen in any future operation.

Find the minimum number of operations required to obtain a set of lists that satisfies the following conditions:

The first element and last element of each list are equal.
The first element of all the lists is the same.

Print -1 if it is not possible to achieve this via any sequence of operations.

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

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains an integer N.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$.

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

For each test case, print a single line containing one integer: the minimum number of operations required to obtain an array of lists that satisfies the given conditions.

Print -1 if it is impossible to achieve such an array of lists.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ N$
- Sum of $N$ over all test cases doesn't exceed $2 \cdot 10^{5}$

------ subtasks ------

Subtask 1(100 points): Original constraints

----- Sample Input 1 ------
3
1
1
2
1 2
3
1 1 2

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

----- explanation 1 ------
Test case $1$: There is only one list $[1]$, and it trivially satisfies the condition so no operations are required.

Test case $2$: There are only $2$ ways to do an operation - either take list $[1]$ and append it to list $[2]$ or take list $[2]$ and append it to list $[1]$. In both cases, it is not possible to satisfy both given conditions at the same time. Hence, the answer is $-1$.

Test case $3$: Here is one possible order of operations:
- Select the $3$rd list $[2]$ and append it to the $1$st list $[1]$.
- Then, select the $2$nd list $[1]$ and append it to the $1$st list $[1, 2]$.

Finally, we are left with the single list $[1, 2, 1]$ which satisfies the given conditions. It can be verified that it is impossible to do this using less than $2$ operations.

见题面

见题面