Description

Input

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

The first line of the description of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of problems in the contest.

The next line contains $n$ integers $a_1,a_2,\ldots a_n$ ($1 \le a_i \le n$) — the tags of the problems.

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

Output

For each test case, if there are no permutations that satisfy the required condition, print $-1$. Otherwise, print the minimum possible cost of a permutation that satisfies the required condition.

4
6
2 1 2 3 1 1
5
1 1 1 2 2
8
7 7 2 7 7 1 8 7
10
1 2 3 4 1 1 2 3 4 1

1
3
-1
2

Note

In the first test case, let $p=[5, 4, 3, 2, 1, 6]$. The cost is $1$ because we jump from $p_5=1$ to $p_6=6$, and $|6-1|>1$. This permutation is valid because we don't solve problems with the same tag twice in a row. We cannot find a permutation with a cost smaller than $1$.

In the second test case, let $p=[1,5,2,4,3]$. The cost is $3$ because $|p_2-p_1|>1$, $|p_3-p_2|>1$, and $|p_4-p_3|>1$. The permutation is valid because we don't solve problems with the same tag twice in a row. We cannot find a permutation with a cost smaller than $3$.

In the third test case, for any order of solving the problems, we will solve two problems with the same tag consecutively, so the answer is $-1$.