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.

Difficulty: MEDIUM
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		m = len(set(a))
		if m == n:
			print(-1)
		else:
			d = {}
			for x in a:
				if x in d:
					d[x] += 1
				else:
					d[x] = 1
			p = max(d.values())
			if p == n:
				print(0)
			else:
				res = n - p + 1
				print(res)


for _ in range(int(input())):
	N = int(input())
	lst = list(map(int, input().split(' ')))
	d = {}
	for ele in lst:
		if ele in d:
			d[ele] += 1
		else:
			d[ele] = 1
	m = max(d.values())
	if m == N:
		print(0)
	elif len(set(lst)) == N:
		print(-1)
	else:
		print(N - m + 1)


t = int(input())
for i in range(t):
	n = int(input())
	z = list(map(int, input().split()))
	d = dict()
	for i in z:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	x = -1
	for i in d:
		x = max(x, d[i])
	if x == n or n == 1:
		print(0)
	elif x == 1 and n != 1:
		print(-1)
	else:
		print(n - x + 1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = {}
	cnt = 0
	for i in arr:
		if i in res:
			res[i] += 1
		else:
			res[i] = 1
		if res[i] > cnt:
			cnt = res[i]
	if cnt == 1 and n > 1:
		print(-1)
	elif n == 1 or n == cnt:
		print(0)
	else:
		print(n - cnt + 1)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	d1 = {}
	for i in arr:
		if i not in d1:
			d1[i] = 1
		else:
			d1[i] += 1
	m1 = max(d1.values())
	if m1 == n:
		print(0)
	elif m1 < 2:
		print(-1)
	else:
		print(n - m1 + 1)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = {}
	for i in a:
		if i in f:
			f[i] += 1
		else:
			f[i] = 1
	m = -1
	for i in f:
		if f[i] > m:
			m = f[i]
	a.sort()
	if n == 1 or a[0] == a[-1]:
		print(0)
	elif m == 1:
		print(-1)
	else:
		print(n - m + 1)


import statistics
from statistics import mode
n = int(input())
for i in range(n):
	q = int(input())
	l = list(map(int, input().split()))
	k = l.count(mode(l))
	if k == 1 and q != 1:
		print(-1)
	elif q == 1 or q == k:
		print(0)
	else:
		h = q - k + 1
		print(h)


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = 1
	c = 1
	a.sort()
	for i in range(n):
		if a[i] == a[i - 1]:
			c += 1
			m = max(m, c)
		else:
			c = 1
	if n == m:
		print(0)
		continue
	if m == 1:
		print(-1)
		continue
	print(n - m + 1)


import sys
T = int(sys.stdin.readline())
for i in range(T):
	N = int(sys.stdin.readline())
	myList = list(map(int, sys.stdin.readline().split()))
	myDict = {}
	maxCounter = 0
	for i in myList:
		if i in myDict:
			myDict[i] += 1
		else:
			myDict[i] = 1
		if myDict[i] > maxCounter:
			maxCounter = myDict[i]
	if maxCounter == 1 and N > 1:
		print(-1)
	elif N == 1:
		print(0)
	elif N == maxCounter:
		print(0)
	else:
		print(N - maxCounter + 1)


from collections import Counter
t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = Counter(a)
	c = b.values()
	if len(b) == 1:
		print(0)
	elif max(c) == 1:
		print(-1)
	else:
		print(sum(c) - max(c) + 1)


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr: enumerate(itr)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def solve(*args, **kwargs):
	(n, arr) = args
	c = Counter(arr)
	if len(c) == 1 and len(c.values()):
		return 0
	if max(c.values()) == 1:
		return -1
	return sum(c.values()) - max(c.values()) + 1

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg1 = inp(int)
		arg3 = inp_vars(int, SPACE)
		res = solve(*(arg1, arg3))
		if type(res) in {list, tuple, set}:
			print(*res, sep=' ')
		else:
			print(res)
main()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = Counter(a)
	values = b.values()
	if len(a) == 1 or len(values) == 1:
		print(0)
	elif max(values) == 1:
		print(-1)
	else:
		print(sum(values) - max(values) + 1)


from collections import Counter
import sys
for i in range(int(input())):
	n = int(input())
	l = list(map(int, sys.stdin.readline().split()))
	d = dict(Counter(l))
	m = max(d.values())
	s = sum(d.values())
	rem = s - m
	if rem == 0:
		print(0)
	elif m > 1:
		print(rem + 1)
	else:
		print(-1)


from collections import Counter
try:
	T = int(input())
	while T > 0:
		N = int(input())
		arr = list(map(int, input().strip().split()))
		if len(set(arr)) == 1:
			print('0')
		elif len(set(arr)) == N:
			print('-1')
		else:
			comm = dict(Counter(arr))
			comm_max = max(comm.values())
			print(N - comm_max + 1)
		T -= 1
except:
	pass


import sys

def _input():
	return sys.stdin.readline().strip()

def main():
	for _ in range(int(_input())):
		n = int(_input())
		lst = list(map(int, _input().split()))
		if len(set(lst)) == 1:
			print(0)
		elif len(set(lst)) == n:
			print(-1)
		else:
			d = {}
			f = 0
			c = d.fromkeys(lst, 0)
			for i in lst:
				if i in c:
					c[i] += 1
			f = max(c.values())
			print(n - f + 1)
main()


from collections import defaultdict
for tc in range(int(input())):
	n = int(input())
	mp = defaultdict(int)
	arr = [int(x) for x in input().split()]
	for num in arr:
		mp[num] += 1
	if len(mp) == 1:
		print('0')
	elif len(mp) == n:
		print('-1')
	else:
		ans = n + 5
		for (key, value) in mp.items():
			if value > 1:
				ans = min(ans, n - value + 1)
		print(ans)


class solution:

	def calc(self):
		tc = int(input())
		for _ in range(tc):
			n = int(input())
			a = [int(x) for x in input().split()]
			m = 1
			c = 1
			a.sort()
			for i in range(n):
				if a[i] == a[i - 1]:
					c += 1
					m = max(m, c)
				else:
					c = 1
			if n == m:
				print(0)
				continue
			if m == 1:
				print(-1)
				continue
			print(n - m + 1)
s = solution()
s.calc()


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1 or len(set(l)) == 1:
		print(0)
	else:
		d = defaultdict(int)
		for i in l:
			d[i] += 1
		m = n + 1
		for i in d.values():
			if i > 1:
				c = n - i + 1
				if m > c:
					m = c
		print(-1) if m == n + 1 else print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	maxCount = 1
	m = {}
	for x in a:
		if x not in m:
			m[x] = 1
		else:
			m[x] += 1
	for freq in m.values():
		maxCount = max(maxCount, freq)
	ans = -1
	if n == 1 or maxCount == n:
		ans = 0
	elif maxCount > 1:
		ans = n - maxCount + 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	length = len(l)
	r = list(set(l))
	d = dict.fromkeys(r, 0)
	for i in l:
		d[i] += 1
	maximum = 0
	for i in d:
		if maximum < d[i]:
			maximum = d[i]
	if maximum == n:
		print(0)
	elif maximum == 1 and len(d.keys()) == n:
		print(-1)
	else:
		print(n - maximum + 1)


from collections import defaultdict
for t in range(int(input())):
	n = int(input())
	np = defaultdict(int)
	arr = [int(x) for x in input().split()]
	for h in arr:
		np[h] += 1
	if len(np) == 1:
		print(0)
	elif len(np) == n:
		print(-1)
	else:
		ans = 0
		for (k, v) in np.items():
			if v > ans:
				ans = v
		print(n - ans + 1)


T = int(input())
for _ in range(T):
	N = int(input())
	LL = list(map(int, input().split()))
	freqDict = dict()
	for item in LL:
		if item in freqDict:
			freqDict[item] += 1
		else:
			freqDict[item] = 1
	maxFrq = max(list(freqDict.values()))
	if maxFrq == 1:
		if len(list(freqDict.keys())) == 1:
			print('0')
		else:
			print('-1')
	elif len(list(freqDict.keys())) == 1:
		print('0')
	else:
		minOper = N - maxFrq + 1
		print(minOper)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mp = defaultdict(int)
	for num in a:
		mp[num] += 1
	if len(mp) == 1:
		print(0)
	elif len(mp) == n:
		print(-1)
	else:
		ans = n + 5
		for (key, value) in mp.items():
			if value > 1:
				ans = min(ans, n - value + 1)
		print(ans)


t = int(input())
while t != 0:
	try:
		n = int(input())
		a = list(map(int, input().split(' ')))
		m = 1
		x = 1
		a.sort()
		for i in range(n):
			if a[i] == a[i - 1]:
				x = x + 1
				m = max(m, x)
			else:
				x = 1
		if n == m:
			print('0')
			continue
		if m == 1:
			print('-1')
			continue
		print(n - m + 1)
	except EOFError:
		break
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	if n == 1:
		print(0)
	else:
		dic = {}
		for item in a:
			if item in dic:
				dic[item] += 1
			else:
				dic[item] = 1
		maximum = 1
		for item in dic:
			if dic[item] > maximum:
				maximum = dic[item]
		if maximum == 1:
			print(-1)
		elif maximum == n:
			print(0)
		else:
			print(n - maximum + 1)


from collections import defaultdict

def minSeq(arr, n):
	freq = defaultdict(int)
	for num in arr:
		freq[num] += 1
	if len(freq) == 1:
		return 0
	elif len(freq) == n:
		return -1
	else:
		ans = n + 10
		for (num, time) in freq.items():
			if time > 0:
				ans = min(ans, n - time + 1)
		return ans
t = int(input())
for z in range(t):
	n = int(input())
	elm = list(map(int, input().split()))
	print(minSeq(elm, n))


t = int(input())
for _ in range(t):
	n = int(input())
	z = input().split()
	l = dict()
	for i in z:
		if i not in l:
			l[i] = 1
		else:
			l[i] += 1
	j = max(list(l.values()))
	x = 0
	sum = 0
	if n == 1 or len(list(l.values())) == 1:
		print(0)
	elif j == 1:
		print(-1)
	else:
		for i in list(l.values()):
			if i != j or x > 0:
				sum += i
			elif x == 0:
				x += 1
		print(sum + 1)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		d = dict()
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		if len(d) == 1:
			get_print_int(0)
		elif len(d) == n:
			get_print_int(-1)
		else:
			get_print_int(n - 1 - (max(d.values()) - 2))
solve()


T = int(input())
from collections import defaultdict
for _ in range(T):
	N = int(input())
	A = map(int, input().split())
	Freq = defaultdict(lambda : 0)
	for a in A:
		Freq[a] += 1
	most_frq = max(Freq.values())
	if most_frq == N:
		print(0)
	elif most_frq < 2:
		print(-1)
	else:
		print(N - most_frq + 1)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	dic = {}
	for i in arr:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	if len(dic) == 1:
		print(0)
	elif len(dic) == n:
		print(-1)
	else:
		ans = n + 2
		for (key, value) in dic.items():
			if value > 1:
				ans = min(ans, n - value + 1)
		print(ans)


nbListe = int(input())
for _ in range(nbListe):
	nbNombre = int(input())
	l = list(map(int, input().split()))
	k = list(set(l))
	d = {}
	d = dict.fromkeys(k, 0)
	for j in l:
		d[j] += 1
	max = 0
	for i in d:
		if max < d[i]:
			max = d[i]
	if max == nbNombre:
		print(0)
	elif max == 1 and len(d.keys()) == nbNombre:
		print(-1)
	else:
		print(nbNombre - max + 1)


t = int(input())
while t:
	t -= 1
	n = int(input())
	elems = [int(i) for i in input().split(' ')]
	freq = {}
	for i in range(len(elems)):
		if elems[i] not in freq:
			freq[elems[i]] = 0
		freq[elems[i]] += 1
	maxf = max(list(freq.values()))
	minops = n - maxf + 1
	if minops == 1:
		print(0)
	elif minops == n:
		print(-1)
	else:
		print(minops)


for a in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if len(set(l)) == 1:
		print(0)
	elif len(set(l)) == len(l):
		print(-1)
	else:
		d = {}
		m = 0
		c = d.fromkeys(l, 0)
		for i in l:
			if i in c:
				c[i] += 1
		m = max(c.values())
		print(len(l) - m + 1)


import sys

def execute(n, values):
	if n == 1:
		return 0
	count_dict = dict()
	max_count = -1
	for val in values:
		if val in count_dict:
			count_dict[val] += 1
		else:
			count_dict[val] = 1
		if count_dict[val] > max_count:
			max_count = count_dict[val]
	if max_count == 1:
		return -1
	if len(count_dict.keys()) == 1:
		return 0
	total_sum = n - max_count - 1 + 2
	return int(total_sum)
t = int(input())
while t:
	t -= 1
	n = int(input())
	values = list(map(int, input().split()))
	print(execute(n, values))


from collections import defaultdict
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = set(A)
	mp = defaultdict(int)
	for num in A:
		mp[num] += 1
	if A.count(A[0]) == N:
		print(0)
	elif sorted(A) == list(S):
		print(-1)
	else:
		ans = N + 5
		for (key, value) in mp.items():
			if value > 1:
				ans = min(ans, N - value + 1)
		print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	if n == 1:
		print(0)
		continue
	for i in range(n):
		if not a[i] in d:
			d[a[i]] = 0
		d[a[i]] += 1
	max_freq = 0
	max_freq_key = 1
	for i in d.keys():
		if d[i] >= max_freq:
			max_freq_key = i
			max_freq = d[i]
	if max_freq == 1:
		print(-1)
	else:
		if max_freq == n:
			print(0)
			continue
		print(n - max_freq + 1)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(input().split())

	def most_frequent(a):
		occurence_count = Counter(a)
		return occurence_count.most_common(1)[0][1]
	f = most_frequent(a)
	ans = n + 1 - most_frequent(a)
	if ans == n and n != 1:
		print(-1)
	elif n == 1 or f == n:
		print(0)
	else:
		print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(0)
	elif len(set(l)) == len(l):
		print(-1)
	else:
		y = 0
		d = {}
		for i in l:
			try:
				d[i] += 1
				if d[i] > y:
					y = d[i]
			except KeyError:
				d[i] = 1
		if n == y:
			print(0)
		else:
			print(n - y + 1)


t = int(input())
for u in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(d, f) = ({}, False)
	(m, ans) = (-2 ** 32, 0)
	for i in l:
		if i in d:
			d[i] += 1
			f = True
		else:
			d[i] = 1
		m = max(m, d[i])
	if f:
		if m == n:
			print(0)
		else:
			ans = n - m
			print(ans + 1)
	elif n == 1:
		print(0)
	else:
		print(-1)


from collections import defaultdict as d
for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	vals = d(int)
	if n == 1 or max(li) == min(li):
		print(0)
	elif len(set(li)) == len(li):
		print(-1)
	else:
		for i in li:
			vals[i] += 1
		min_val = n + 5
		for (i, j) in vals.items():
			if n - j + 1 < min_val and j > 1:
				min_val = n - j + 1
		print(min_val)


from collections import Counter
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	freq = Counter(A)
	max_freq = max(freq.values())
	if N == max_freq:
		print(0)
	elif N == len(freq.keys()):
		print(-1)
	else:
		print(N - max_freq + 1)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for num in arr:
		if num in d:
			d[num] += 1
		else:
			d[num] = 1
	max_freq = max(d.values())
	if n == 1 or max_freq == n:
		print(0)
	elif max_freq >= 2:
		print(n - max_freq + 1)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	freq = {}
	for item in l:
		if item in freq:
			freq[item] += 1
		else:
			freq[item] = 1
	maxi = max(freq.values())
	if len(l) == 1:
		print(0)
	elif maxi == 1:
		print(-1)
	elif maxi == len(l):
		print(0)
	else:
		print(len(l) - maxi + 1)


from collections import Counter
try:
	for _ in range(int(input())):
		N = int(input())
		numbers = list(map(int, input().split()))
		cc = Counter(numbers)
		s = list(set(numbers))
		if len(numbers) == 1 or len(s) == 1:
			print(0)
		elif len(numbers) == 2:
			print(-1)
		elif len(s) == len(numbers):
			print(-1)
		else:
			maxed = cc.most_common()
			rep = maxed[0][1]
			total = len(numbers) + 1 - rep
			print(total)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	freq = {}
	for i in a:
		if i in freq:
			freq[i] += 1
		else:
			freq[i] = 1
	if len(freq) == 1:
		print(0)
		continue
	if len(freq) == n:
		print(-1)
		continue
	ans = float('inf')
	for i in freq:
		if freq[i] > 1:
			ans = min(n - freq[i] + 1, ans)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	dic = {}
	arr = list(map(int, input().split()))
	for i in arr:
		if i not in dic.keys():
			dic[i] = 1
		else:
			dic[i] += 1
	if len(dic) == 1:
		print(0)
	elif len(dic) == n:
		print(-1)
	else:
		print(n - max(dic.values()) + 1)


try:
	t = input()
	for i in range(int(t)):
		n = input()
		a = input()
		l = list(map(int, a.split(' ')))
		mx = 1
		c = 1
		l.sort()
		for k in range(1, int(n)):
			if l[k] == l[k - 1]:
				c += 1
				mx = max(mx, c)
			else:
				c = 1
		if int(n) == mx:
			print(0)
		elif mx == 1:
			print(-1)
		else:
			print(int(n) - mx + 1)
except EOFError as e:
	print()


t = int(input())
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	dic = {}
	if n == 1:
		print('0')
	else:
		max_total = 0
		max_no = 0
		for i in range(n):
			if a[i] not in dic:
				dic[a[i]] = 1
			else:
				dic[a[i]] = dic[a[i]] + 1
			if dic[a[i]] > max_total:
				max_total = dic[a[i]]
				max_no = a[i]
		if max_total == 1:
			print('-1')
		elif max_total == n:
			print('0')
		else:
			print(n - max_total + 1)


for t in range(int(input())):
	n = int(input())
	di = {}
	val = 1
	li = list(map(int, input().split()))
	if len(li) < 2:
		print(0)
	else:
		for i in li:
			val = i
			if val in di:
				di[val] += 1
			else:
				di[val] = 1
		if len(di) == n:
			print(-1)
		elif len(di) == 1:
			print(0)
		else:
			maxi = max(di.values())
			print(n - maxi + 1)


for t in range(int(input())):
	n = int(input())
	di = {}
	val = 1
	li = list(map(int, input().split()))
	if len(li) < 2:
		print(0)
	else:
		for i in li:
			val = i
			if val in di:
				di[val] += 1
			else:
				di[val] = 1
		if len(di) == n:
			print(-1)
		elif len(di) == 1:
			print(0)
		else:
			min1 = n + 3
			for i in di:
				if di[i] > 1:
					min1 = min(min1, n - di[i] + 1)
			print(min1)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	num_unique = len(set(arr))
	if num_unique == 1:
		print(0)
	elif num_unique == n:
		print(-1)
	else:
		c = Counter(arr)
		max_freq = max(c.values())
		ans = n - max_freq + 1
		print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	lists = map(int, input().split())
	if n <= 1:
		print(0)
		continue
	c = Counter(lists)
	freq = c.most_common(1)[0][1]
	if freq == n:
		print(0)
		continue
	if freq == 1:
		print(-1)
		continue
	print(n - freq + 1)


t = int(input())
for _ in range(t):
	number = int(input())
	list_number = list(map(int, input().split()))
	set_numbers = list(set(list_number))
	l = len(set_numbers)
	if number == 1:
		print(0)
	elif l == 1:
		print(0)
	elif len(list_number) == l:
		print(-1)
	else:
		list_number.sort()
		last = 0
		max_freq = 0
		for i in range(0, number - 1):
			freq = 0
			if list_number[i] != list_number[i + 1]:
				freq = i + 1 - last
				last = i + 1
			if max_freq < freq:
				max_freq = freq
		if number - last > max_freq:
			max_freq = number - last
		print(number + 1 - max_freq)


for _ in range(int(input())):
	n = map(int, input().split())
	l = list(map(int, input().split()))
	if len(l) == 1:
		print(0)
	elif len(l) == len(set(l)):
		print(-1)
	else:
		d = dict()
		for x in l:
			if x not in d.keys():
				d[x] = 1
			else:
				d[x] += 1
		malele = max(d.values())
		if malele == len(l):
			print(0)
		else:
			ans = len(l) - malele + 1
			print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	if n == 1:
		print(0)
	else:
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		m = m1 = 0
		for i in d.keys():
			if m < d[i]:
				m = d[i]
				m1 = i
		if n - m + 1 == n:
			print(-1)
		elif n - m + 1 == 1:
			print(0)
		else:
			print(n - m + 1)


T = int(input())
for test in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	if N == 0:
		print(-1)
	elif N == 1:
		print(0)
	elif len(set(A)) == 1:
		print(0)
	else:
		mx = 1
		c = 1
		A.sort()
		for i in range(N):
			if A[i] == A[i - 1]:
				c += 1
				mx = max(mx, c)
			else:
				c = 1
		if mx == N:
			print(0)
		elif mx == 1:
			print(-1)
		else:
			print(N - mx + 1)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l)
	x = c.most_common(1)[0][1]
	if n == 1 or x == len(l):
		print(0)
	elif n >= 2 and x <= 1:
		print(-1)
	else:
		print(len(l) - x + 1)


for _ in range(int(input())):
	n = int(input())
	a = [0] * n
	a = list(map(int, input().split()))
	mx = 1
	c = 1
	a.sort()
	for i in range(n):
		if a[i] == a[i - 1]:
			c = c + 1
			mx = max(mx, c)
		else:
			c = 1
	if n == mx:
		print(0)
		continue
	if mx == 1:
		print(-1)
		continue
	print(n - mx + 1)


from collections import Counter
t = int(input())
for i in range(t):
	z = int(input())
	l = list(map(int, input().split()))
	a = Counter(l)
	b = -1
	c1 = -1
	for (m, n) in a.items():
		b = max(b, n)
	for (m, n) in a.items():
		if n == b:
			c1 = m
			break
	if z == 1 or len(set(l)) == 1:
		print(0)
	elif b == 1:
		print(-1)
	else:
		c2 = a[c1]
		c3 = z - c2
		print(c3 + 1)


def listof():
	for i in range(int(input())):
		n = int(input())
		a = [int(x) for x in input().split()]
		a.sort()
		m = 1
		c = 1
		for i in range(n):
			if a[i] == a[i - 1]:
				c += 1
				m = max(m, c)
			else:
				c = 1
		if n == m:
			print(0)
			continue
		if m == 1:
			print(-1)
			continue
		print(n - m + 1)
listof()


t = int(input())
for i in range(t):
	n = int(input())
	d = {}
	m = 0
	l = input().split(' ')
	for j in l:
		if j in d:
			d[j] += 1
			if d[j] >= 2 and d[j] > m:
				m = d[j]
		else:
			d[j] = 1
	if len(d.keys()) == 1:
		print(0)
	elif m == 0:
		print(-1)
	else:
		print(int(n - (m - 2) - 1))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	m = 1
	c = 1
	for i in range(n):
		if a[i] == a[i - 1]:
			c += 1
			m = max(m, c)
		else:
			c = 1
	if n == m:
		print('0', end='')
		continue
	if m == 1:
		print('-1')
		continue
	print(n - m + 1)


for i in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	(b, c) = (1, 1)
	a.sort()
	for i in range(1, x):
		if a[i] == a[i - 1]:
			c += 1
			b = max(b, c)
		else:
			c = 1
	if x == b:
		print('0')
		continue
	if b == 1:
		print('-1')
		continue
	print(x - b + 1)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = Counter(a)
	m = max(l, key=l.get)
	h = l[m]
	if h == len(a):
		print(0)
	elif h >= 2:
		print(len(a) - h + 1)
	else:
		print('-1')


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	list1 = list(map(int, input().split()))
	c = Counter(list1)
	y = c.most_common(1)[0][1]
	if n == 1 or y == len(list1):
		print(0)
	elif n >= 2 and y <= 1:
		print(-1)
	else:
		print(len(list1) - y + 1)