M. Jebreel loves Chelsea (Brown)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Leo stood in the damp shadows of the sewer lair, sliding a heavy briefcase toward Jebreel. Inside lay a crisp, royal blue Chelsea jersey and a stack of VIP passes to Stamford Bridge. Jebreel's hand shook as he took it; he was wearing his favorite Liverpool kit, and the thought of covering the Liver bird with Chelsea blue felt like a personal betrayal. To seal the deal, Jebreel pulled the blue shirt on, the Chelsea crest resting directly over his heart.

Jebreel With Chelsea jersey

You are given an array $$$a$$$ of $$$n$$$ integers. In one operation, you can choose an index $$$i$$$ ($$$1 \le i \le n$$$) and replace $$$a_i$$$ with the number of times its current value appears in the suffix $$$a_i, a_{i+1}, \dots, a_n$$$.

Find the minimum number of operations required to make all elements in the array equal. If it is impossible to make all elements equal, output $$$-1$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — denotes the length of the array $$$a$$$.

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

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

Output

For each test case, output a single integer — the minimum number of operations required to make all elements equal. If it is impossible, output $$$-1$$$.

Example
Input
2
3
7 7 7
2
1 2
Output
0
1
Note

In the first test case, the array is initially $$$[7, 7, 7]$$$. All elements are already equal, so the number of operations required is $$$0$$$.

In the second test case, the array is initially $$$[1, 2]$$$. If we choose index $$$i=2$$$, $$$a_2$$$ is replaced by the count of $$$2$$$ in the suffix $$$[2]$$$, which is $$$1$$$. The array becomes $$$[1, 1]$$$. The minimum number of operations is $$$1$$$.