Chef is teaching his class of N students at Hogwarts. He groups students with the same height together for an activity. Some of the students end up in a groups with only themselves and are saddened by this.

With the help of his magic wand, Chef can increase the height of any student to any value he likes. Now Chef wonders, what is the minimum number of students whose height needs to be increased so that there are no sad students?

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains one integer N — the number of students.
- The second line consists of N space-separated integers H_{1}, H_{2}, \ldots, H_{N} denoting the heights of the students.

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

For each test case, output on a single line the minimum number of students whose heights must to be increased.

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

$1 ≤ T ≤ 5\cdot 10^{4}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ H_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
4
1 2 1 2
4
1 2 2 2
3
1 1 1
5
1 2 3 4 5

----- Sample Output 1 ------ 
0
1
0
3

----- explanation 1 ------ 
Test case $1$: The students form $2$ groups each having $2$ students so no change of heights is required.

Test case $2$: Initially the student with height $1$ cannot be paired with anyone else. Chef can increase his height to $2$ and now there is only $1$ group with all the $4$ students in it.

Test case $3$: All students have same height and hence no change of heights is required.

Test case $4$: One possible way is to increase the height of the first student to $5$ and the heights of the second and third students to $4$, hence forming one group of $2$ students and one of  $3$ students. In total, the heights of $3$ students need to be changed.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	unique = 0
	unique_dict = {}
	for ele in num:
		if ele in unique_dict:
			unique_dict[ele] += 1
		else:
			unique_dict[ele] = 1
	unique = list(unique_dict.values())
	if num.count(max(num)) == 1 and unique.count(2) == len(unique) - 1:
		print('2')
	else:
		print((unique.count(1) + 1) // 2)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = dict(Counter(a))
	b = 0
	c = max(a.keys())
	if a[c] == 1:
		(pos, one) = (0, 0)
		for (x, y) in a.items():
			if x != c:
				if y == 1:
					one = 1
					a[x] -= 1
					a[c] += 1
					b += 1
					break
				elif y > 2:
					pos = x
		if not one:
			if pos:
				a[c] += 1
				b += 1
			else:
				b += 2
				a[c] += 2
	d = 0
	for (x, y) in a.items():
		if y == 1:
			d += 1
	print((d + 1) // 2 + b)


t = int(input())
for t in range(t):
	n = int(input())
	h = [int(i) for i in input().split()]
	d = {}
	ans = 0
	for k in h:
		if k in d:
			d[k] += 1
		else:
			d[k] = 1
	arr = list(d.values())
	count = arr.count(1)
	if h.count(max(h)) == 1 and arr.count(2) == len(arr) - 1:
		ans = 2
	else:
		ans = (count + 1) // 2
	print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = list(Counter(arr).values())
	if arr.count(max(arr)) == 1 and c.count(2) == len(c) - 1:
		print(2)
	else:
		p = c.count(1)
		print((p + 1) // 2)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	d = {}
	for i in range(n):
		if str(arr[i]) not in d.keys():
			d[str(arr[i])] = 1
		else:
			d[str(arr[i])] = d[str(arr[i])] + 1
	x = list(d.values()).count(1)
	y = list(d.values()).count(2)
	if d[str(max(arr))] == 1 and y == len(d) - 1:
		print('2')
	else:
		print((x + 1) // 2)


from collections import Counter
t = int(input())
for h in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = Counter(l)
	L = 0
	m = 0
	h = 0
	for i in k:
		if k[i] == 1:
			L += 1
			m += 1
			if m == 1:
				h = i
	ans = (L + 1) // 2
	if m == 1 and h == max(l):
		ans = 2 * n
		for i in k:
			if k[i] != 1:
				if k[i] >= 3:
					ans = 1
					break
				ans = min(ans, k[i])
	print(ans)


for _ in range(int(input())):
	N = int(input())
	H = list(map(int, input().split()))
	H.sort()
	flag = 0
	i = 0
	if N == 2:
		if H[0] != H[1]:
			flag += 1
		else:
			flag = 0
	else:
		while i < N - 1:
			if i == 0:
				if H[i] != H[i + 1]:
					flag += 1
			elif H[i] == H[i + 1] or H[i] == H[i - 1]:
				i += 1
				continue
			else:
				flag += 1
			i += 1
	if H[N - 1] != H[N - 2]:
		flag += 1
	if H[N - 1] != H[N - 2] and flag == 1 and (N % 2 == 0):
		flag += 1
	elif H[N - 1] != H[N - 2] and flag == 1 and (N % 2 == 1):
		flag += 2
	if flag == 0:
		print(0)
	elif flag % 2 == 0:
		print(flag // 2)
	elif flag % 2 == 1:
		print(flag // 2 + 1)


from collections import Counter
t = int(input())
for index in range(t):
	n = int(input())
	data = list(map(int, input().split()))
	data_count = Counter(data)
	count = 0
	for i in data_count.keys():
		if data_count[i] == 1:
			count += 1
	max_data = max(data)
	if count == 1 and data_count[max_data] == 1:
		data_count.pop(max_data)
		c = 0
		for j in data_count.keys():
			if data_count[j] > 2:
				print(1)
				c = 1
				break
		if c == 0:
			print(2)
	else:
		print((count + 1) // 2)


import math
for l in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	ans = 0
	count = 0
	x = 0
	for i in d:
		if d[i] == 1:
			ans += 1
			x = i
		elif d[i] == 2:
			count += 1
	if len(d) - 1 == count and ans == 1 and (x == max(d)):
		print(2)
		continue
	print(math.ceil(ans / 2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	maxi = a[0]
	g = 0
	for num in a:
		maxi = max(maxi, num)
		if num not in d:
			d[num] = 1
		else:
			d[num] += 1
		if d[num] > 2:
			g += 1
	res = 0
	for val in d.values():
		if val == 1:
			res += 1
	if n > 2 and d[maxi] == 1 and (res == 1) and (g == 0):
		print(2)
		continue
	print(res // 2 + res % 2)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = list(Counter(arr).keys())
	y = list(Counter(arr).values())
	count = 0
	c2 = 0
	f = len(y)
	flag = 0
	w = 0
	for i in range(f):
		if y[i] == 1:
			count += 1
			w = i
		if y[i] == 2:
			c2 += 1
	if count == 1:
		if int(x[w]) == max(arr) and c2 == f - 1:
			print('2')
			flag = flag + 1
	if flag == 0:
		print((count + 1) // 2)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	d = {}
	for i in range(n):
		if str(arr[i]) not in d.keys():
			d[str(arr[i])] = 1
		else:
			d[str(arr[i])] = d[str(arr[i])] + 1
	count = 0
	c2 = 0
	w = 0
	x = list(d.keys())
	y = list(d.values())
	f = len(y)
	flag = 0
	for i in range(f):
		if y[i] == 1:
			count += 1
			w = i
		if y[i] == 2:
			c2 += 1
	if count == 1:
		if int(x[w]) == max(arr) and c2 == f - 1:
			print('2')
			flag = flag + 1
	if flag == 0:
		print((count + 1) // 2)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(count, maxx, maxx_v) = (0, 0, 0)
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d:
		if d[i] == 1:
			count += 1
		maxx = max(maxx, i)
		maxx_v = max(maxx_v, d[i])
	if count != 1:
		print((count + 1) // 2)
	elif d[maxx] == 1:
		if maxx_v == 2:
			print(2)
		else:
			print(1)
	else:
		print(1)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s1 = set()
	grp = set()
	s = input()
	s = s.split()
	flag = 2
	max = 0
	for i in range(n):
		if max < int(s[i]):
			max = int(s[i])
		if s[i] in s1 or s[i] in grp:
			if s[i] in grp:
				flag = 1
			grp.add(s[i])
			s1.discard(s[i])
		else:
			s1.add(s[i])
	res = int((len(s1) + 1) / 2)
	if len(s1) == 1 and max == int(s1.pop()):
		print(flag)
	else:
		print(res)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cou = Counter(arr)
	co = list(cou.items())
	lis = []
	for (i, j) in co:
		if j == 1:
			lis.append(i)
	if max(arr) in lis:
		if len(lis) == 1:
			val = max(cou.values())
			if val == 2:
				print(2)
			else:
				print(1)
			continue
	if len(lis) % 2 == 0:
		print(int(len(lis) / 2))
	else:
		print(int(len(lis) / 2) + 1)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	freq = {}
	for i in l:
		freq[i] = 0
	for i in range(n):
		freq[l[i]] += 1
	alone = 0
	u = -1
	max_element = -1
	max_freq = 0
	for i in range(n):
		max_element = max(max_element, l[i])
		max_freq = max(max_freq, freq[l[i]])
		if freq[l[i]] == 1:
			alone += 1
			u = l[i]
	if max_freq == 2 and max_element == u and (alone == 1):
		print(2)
		continue
	print((alone + 1) // 2)


from collections import Counter
from math import ceil
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = Counter(arr)
	val = list(cnt.values()).count(1)
	ans = ceil(val / 2)
	if val != 1 or cnt[max(arr)] != 1:
		print(ans)
	else:
		cnt.pop(max(arr))
		k = max(cnt.values())
		if k == 2:
			print(2)
		else:
			print(1)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	s = set(lst)
	d = {}
	for i in s:
		d[i] = 0
	for i in lst:
		d[i] += 1
	sad = []
	for i in d:
		if d[i] == 1:
			sad.append(i)
	maxi = max(lst)
	flag = 0
	if maxi in sad:
		if len(sad) == 1:
			a = list(d.values())
			maxi = max(a)
			if maxi == 2:
				print(2)
			else:
				print(1)
			continue
	if len(sad) % 2 == 0:
		print(int(len(sad) / 2))
	else:
		print(int(len(sad) / 2) + 1)


(t, n) = (int(input()), 1)
while n <= t:
	(l, mag) = (int(input()), list(map(int, input().split())))
	(cm, c, chk) = ({}, 0, 0)
	for i in mag:
		if i not in cm:
			cm[i] = 1
		else:
			cm[i] += 1
	for keys in cm.values():
		if keys == 1:
			c += 1
	if c == 0:
		print('0')
	elif cm[max(mag)] == 1 and c == 1:
		for keys in cm.values():
			if keys >= 3:
				chk = 3
				print('1')
				break
			elif keys == 2:
				chk = 2
		if chk == 2:
			print('2')
	else:
		print((c + 1) // 2)
	n += 1


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


for i in range(int(input())):
	n = input()
	h = map(int, input().split())
	group_numbers = {}
	for j in h:
		if j in group_numbers:
			group_numbers[j] += 1
		else:
			group_numbers[j] = 1
	value_list = list(group_numbers.values())
	x = value_list.count(1)
	y = x // 2
	if x % 2 == 0:
		print(y)
	elif x == 1 and group_numbers[max(list(group_numbers.keys()))] == 1 and (max(value_list) <= 2):
		print(y + 2)
	else:
		print(y + 1)


from collections import Counter

def findLoneWolf(heights):
	lone_height = 0
	c_heights = Counter(heights)
	max_frequency = 0
	max_height = 0
	for (height, count) in c_heights.items():
		if count == 1:
			lone_height += 1
		max_frequency = max(max_frequency, count)
		max_height = max(max_height, height)
	if lone_height == 1 and c_heights[max_height] == 1:
		return 1 if max_frequency > 2 else 2
	else:
		return (lone_height + 1) // 2
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(findLoneWolf(A))


for _ in range(int(input())):
	n = int(input())
	heights = dict()
	max_height = 0
	l = list(map(int, input().rstrip().split()))
	for ele in l:
		heights[ele] = heights.get(ele, 0) + 1
		max_height = max(max_height, ele)
	count = 0
	good_count = 0
	largest = False
	for (k, v) in heights.items():
		if heights[k] == 1:
			count += 1
			if k == max_height:
				largest = True
		elif heights[k] > 2:
			good_count += 1
	if count == 1:
		if good_count or not largest:
			print(1)
		else:
			print(2)
	else:
		print((count + 1) // 2)


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import Counter

def solve():
	n = ri()
	C = Counter(rl())
	MAX = flag = 0
	sad = []
	for (k, v) in C.items():
		if v == 1:
			sad.append(k)
		if v > 2:
			flag = 1
		MAX = max(MAX, k)
	if not sad:
		return 0
	if len(sad) > 1:
		return len(sad) - len(sad) // 2
	if sad[0] != MAX or flag:
		return 1
	return 2

def main():
	for _ in range(ri()):
		print(solve())
main()


from collections import Counter
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(Counter(a).values())
	if a.count(max(a)) == 1 and d.count(2) == len(d) - 1:
		print(2)
	else:
		c = d.count(1)
		print((c + 1) // 2)


import math
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	l.sort(reverse=True)
	gret = 0
	cou = 0
	if l[0] != l[1]:
		gret = 1
		count = 1
	else:
		count = 2
	alone = 0
	gt = 0
	for i in range(1, n - 1):
		if l[i] != l[i + 1]:
			if count == 1:
				alone += 1
			count = 1
		else:
			count += 1
		if count > 2:
			gt = 1
	if count == 1:
		alone += 1
	if gret == 1:
		if alone == 0:
			if gt == 1:
				print(1)
			else:
				print(2)
			continue
		else:
			alone += 1
	print(math.ceil(alone / 2))


import math
l = int(input())
tests = []
for h in range(l):
	o = input()
	test = list(map(int, input().split()))
	tests.append(test)

def solve(v):
	singlur = set()
	muli = set()
	moreThanOne = {}
	moreThanOneBool = False
	for h in v:
		if h in muli:
			count = moreThanOne.get(h, 2)
			moreThanOne[h] = count + 1
			if moreThanOne[h] > 2:
				moreThanOneBool = True
			continue
		if h in singlur:
			singlur.remove(h)
			muli.add(h)
			continue
		singlur.add(h)
	if len(singlur) == 1 and list(singlur)[0] == max(v):
		if moreThanOneBool:
			return 1
		else:
			return 2
	students = math.ceil(len(singlur) / 2)
	return students
for s in tests:
	print(solve(s))


n = int(input())
while n:
	m = int(input())
	l = list(map(int, input().split()))
	s = list(set(l))
	pp = 0
	g = []
	d = {}
	for i in l:
		try:
			d[i] += 1
		except:
			d[i] = 1
	for i in d:
		if d[i] > 1:
			if d[i] > 2:
				pp = 1
			else:
				pass
		else:
			g.append(i)
	if len(g) < 1:
		print(0)
	else:
		u = len(g)
		p = u // 2
		if u % 2 == 1:
			p += 1
		if u == 1 and g[0] == max(s):
			if pp == 1:
				p = 1
			else:
				p = 2
		print(p)
	n -= 1


import math
T = int(input())
for t in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	x = [0] * max(max(l), n)
	l1 = []
	for i in l:
		x[i - 1] += 1
	while x[-1] == 0:
		x.pop()
	ans = x.count(1)
	if ans == 1:
		if x[-1] == 1:
			x.pop()
			if max(x) == 2:
				print(2)
				continue
	print(math.ceil(ans / 2))


n1 = int(input())
for i in range(n1):
	y = int(input())
	x = [int(a) for a in input().split()]
	x.sort()
	pos1 = 0
	max = x[0]
	l2 = []
	c = 0
	for i in range(len(x)):
		if max < x[i]:
			if i - pos1 == 1:
				c += 1
			l2.append((x[i - 1], i - pos1))
			pos1 = i
			max = x[i]
	l2.append((x[-1], len(x) - pos1))
	if len(x) - pos1 == 1:
		c += 1
	if c == 1 and len(x) - pos1 == 1:
		s = 2
		for i in range(len(l2) - 1):
			if l2[i][1] != 2:
				s = 1
		print(s)
	elif c % 2 == 0:
		print(c // 2)
	else:
		print(c // 2 + 1)


import math
for _ in range(1, int(input()) + 1):
	n = int(input())
	arr = [int(i) for i in input().split()]
	heights = dict()
	for i in arr:
		if i in heights:
			heights[i] += 1
		else:
			heights[i] = 1
	count = 0
	for i in heights:
		if heights[i] == 1:
			count += 1
	if count != 1:
		print(math.ceil(count / 2))
	elif heights[max(heights)] == 1:
		done = False
		for i in heights:
			if heights[i] >= 3:
				print(1)
				done = True
				break
		if not done:
			print(2)
	else:
		print(1)


t = int(input())
for i in range(t):
	x = int(input())
	l = list(map(int, input().split()))
	countDict = {}
	single = 0
	mx = max(l)
	gp3 = 0
	for i in l:
		try:
			countDict[i] += 1
		except:
			countDict[i] = 1
	maxele = countDict[mx]
	for i in countDict.keys():
		if countDict[i] == 1:
			unique = i
			single += 1
		if countDict[i] > 2:
			gp3 += 1
	if single == 1:
		if unique != mx:
			print(1)
		elif unique == mx and gp3 > 0:
			print(1)
		elif unique == mx and gp3 == 0:
			print(2)
	else:
		print(int((single + 1) // 2))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	l.sort()
	c = 0
	m = 0
	mk = 0
	d = {}
	for i in l:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	for (k, v) in d.items():
		if v == 1:
			c += 1
		m = max(m, v)
		mk = max(mk, k)
	if c == 1:
		if d[mk] == 1 and m == 2:
			print(2)
		else:
			print(1)
	else:
		if c % 2 == 0:
			res = c // 2
		else:
			res = c // 2 + 1
		print(res)


from math import ceil
for _ in range(int(input())):
	numberOfElements = int(input())
	heights = list(map(int, input().split()))
	counter = 0
	specialCase = False
	d = {}
	maxValue = 0
	for x in heights:
		d[x] = d.get(x, 0) + 1
		if x > maxValue:
			maxValue = x
	maxFreq = 0
	numberOfElementsWithOne = 0
	for val in d.values():
		if val == 1:
			numberOfElementsWithOne += 1
		maxFreq = max(maxFreq, val)
	for j in d.values():
		if j == 1:
			if d[maxValue] == 1 and numberOfElementsWithOne == 1 and (maxFreq == 2):
				specialCase = True
				print(maxFreq)
				break
			else:
				counter += 1
	if not specialCase:
		print(int(ceil(counter / 2)))


for _ in range(int(input())):
	pass
	numberOfElements = int(input())
	height = list(map(int, input().split()))
	counter = 0
	specialCase = False
	d = {}
	maxValue = 0
	for x in height:
		d[x] = d.get(x, 0) + 1
		if x > maxValue:
			maxValue = x
	list1 = list(d.values())
	numberOfElementsWithOne = list1.count(1)
	noMaxElements = max(d.values())
	for j in d.values():
		if j == 1:
			if j == d[maxValue] and numberOfElementsWithOne == 1 and (noMaxElements == 2):
				counter += noMaxElements
				specialCase = True
				print(counter)
				break
			else:
				counter += 1
	if not specialCase:
		if counter % 2 == 0:
			print(int(counter / 2))
		else:
			print(int((counter + 1) / 2))


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	size = max(l) + 1
	dp = {}
	for i in l:
		if i in dp:
			dp[i] += 1
		else:
			dp[i] = 1
	arr = []
	for i in dp:
		if dp[i] == 1:
			arr.append(i)
	if len(arr) == 0:
		print(0)
	elif len(arr) == 1 and arr[0] == max(l):
		p = sorted(dp.values())
		mx = max(p)
		if mx > 2:
			print(1)
		else:
			print(2)
	else:
		print((len(arr) + 1) // 2)
	t -= 1


numberOfTestCases = int(input())
while numberOfTestCases >= 1:
	numberOfElements = int(input())
	height = list(map(int, input().split()))
	counter = 0
	specialCase = False
	d = {}
	maxValue = 0
	for x in height:
		d[x] = d.get(x, 0) + 1
		if x > maxValue:
			maxValue = x
	list1 = list(d.values())
	numberOfElementsWithOne = list1.count(int(1))
	for j in d.values():
		if j == 1:
			if j == d[maxValue] and numberOfElementsWithOne == 1:
				specialCase = True
			else:
				counter += 1
	if specialCase:
		d.pop(maxValue)
		noMaxElements = max(d.values())
		if noMaxElements == 2:
			counter += noMaxElements
		else:
			counter += 1
		print(counter)
	elif counter % 2 == 0:
		print(int(counter / 2))
	else:
		print(int((counter + 1) / 2))
	numberOfTestCases -= 1


import math
for i in range(int(input())):
	n = int(input())
	h = [int(i) for i in input().split()]
	d = {}
	for j in h:
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
	m = []
	for j in d:
		if d[j] == 1:
			m.append(j)
	if m == []:
		print(0)
	elif len(m) == 1 and m[0] == max(h):
		sh = sorted(d.values())
		if max(sh) > 2:
			print(1)
		else:
			print(2)
	else:
		print(math.ceil(len(m) / 2))


import math
t = int(input())
while t > 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	s = []
	for i in d:
		if d[i] == 1:
			s.append(i)
	if s == []:
		print(0)
	elif len(s) == 1 and s[0] == max(a):
		m = sorted(d.values())
		if max(m) > 2:
			print(1)
		else:
			print(2)
	else:
		print(math.ceil(len(s) / 2))
	t -= 1


from collections import Counter

def m(l):
	a = []
	for i in l:
		a.append(c[i])
	return max(a)
T = int(input())
for tc in range(0, 2 * T):
	if tc % 2 == 1:
		a = input().split(' ')
		H = []
		for i in a:
			H.append(int(i))
		c = Counter(H)
		count = 0
		for i in H:
			if c[i] == 1:
				count += 1
		if count < 2:
			if c[max(H)] == 1:
				if m(H) > 2:
					print(int(1))
				else:
					print(int(2))
			else:
				print(count)
		elif count % 2 == 0:
			print(int(count / 2))
		else:
			print(int(count / 2 + 0.5))
	else:
		N = int(input())


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = dict(Counter(arr))
	one_freqs = 0
	for (num, fr) in freq.items():
		one_freqs += fr == 1
	max_num_freq = freq[max(arr)]
	frs = sorted(list(freq.values()))
	if one_freqs == 0:
		print(0)
	elif one_freqs > 1:
		print(one_freqs // 2 + one_freqs % 2)
	elif max_num_freq == 1:
		if frs[-1] > 2:
			print(1)
		else:
			print(2)
	else:
		print(1)


from collections import Counter
import math
T = int(input())
for _ in range(T):
	N = int(input())
	count = 0
	co = 0
	k = 0
	H = list(map(int, input().split()))
	height = Counter(H)
	h = list(height.keys())
	h = sorted(h, reverse=True)
	f = h[0]
	for i in h:
		k += 1
		if height[i] == 1:
			if count == 0:
				co += 1
				count = 1
			else:
				count = 0
	if count == 1 and height[i] == 2 and (height[f] == 1) and (N - 2 * k != 0):
		co += 1
	print(co)


for XD in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = {}
	nl = 0
	maxFreq = 0
	for i in l:
		try:
			m[i] += 1
			maxFreq = max(maxFreq, m[i])
		except:
			m[i] = 1
	cnt = 0
	for i in l:
		if m[i] == 1:
			cnt += 1
			nl = i
	if cnt % 2 == 0:
		print(cnt // 2)
	elif cnt == 1:
		if nl == max(l) and maxFreq == 2:
			print(2)
		else:
			print(1)
	else:
		print(cnt // 2 + 1)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = Counter(arr)
	left = 0
	mv = 0
	for (k, v) in c.items():
		if v > mv:
			mv = v
		if v == 1:
			left += 1
	if left == 1:
		arr.sort()
		if c[arr[-1]] != 1:
			print(1)
		elif mv > 2:
			print(1)
		else:
			print(2)
	elif left % 2 == 0:
		print(left // 2)
	else:
		print(left // 2 + 1)


def ans(arr):
	hm = {}
	for y in arr:
		if y in hm.keys():
			hm[y] += 1
		else:
			hm[y] = 0
	count = 0
	arr2 = []
	for y in hm.keys():
		if hm[y] == 0:
			arr2.append(y)
			count += 1
	if count == 1 and max(arr2) == max(arr):
		for y in hm.values():
			if y >= 2:
				return 1
		return 2
	else:
		return min(count, count // 2 + count % 2)
test_cases = int(input())
while test_cases != 0:
	d_ = input()
	d = list(map(int, input().split()))
	print(ans(d))
	test_cases -= 1


from collections import Counter
from math import ceil
for i in range(int(input())):
	_ = input()
	inp = list(map(int, input().split()))
	heights = Counter(inp)
	counts = Counter(heights.values())
	if counts[1] == 1:
		lonely = [height for (height, count) in heights.items() if count == 1][0]
		for (height, count) in heights.items():
			if count > 2 or height > lonely:
				print(1)
				break
		else:
			print(2)
	else:
		print((counts[1] + 1) // 2)


def solve():
	n = int(input())
	H = list(map(int, input().split()))
	H.sort()
	counts = []
	sad = 0
	mp = {}
	for i in range(n):
		if H[i] in mp.keys():
			mp[H[i]] += 1
		else:
			mp[H[i]] = 1
	counts = list(mp.values())
	sad = counts.count(1)
	if sad == 1 and n % 2 != 0:
		if H.count(H[n - 1]) == 1:
			sad = min(filter(lambda x: x > 1, counts)) * 2
	if sad % 2 == 0:
		print(sad // 2)
	else:
		print((sad + 1) // 2)
t = int(input())
while t > 0:
	solve()
	t -= 1


from collections import Counter
t = int(input())
while t != 0:
	i = 0
	c = 0
	n = int(input())
	arr = list(map(int, input().split()))
	d = Counter(sorted(arr))
	ls_loner = list([x for x in d if d[x] == 1])
	if len(ls_loner) == 0:
		print(0)
	elif len(ls_loner) == 1:
		if ls_loner[0] == max(arr):
			ls_pair = list([x for x in d if d[x] > 2])
			if len(ls_pair) != 0:
				print(1)
			else:
				print(2)
		else:
			print(1)
	else:
		while True:
			try:
				if len(ls_loner) == 0:
					break
				if len(ls_loner) > 3 or len(ls_loner) % 2 == 0:
					ls_loner[i] = ls_loner[i] + (ls_loner[i + 1] - ls_loner[i])
					c += 1
					ls_loner.pop(0)
					ls_loner.pop(1)
				else:
					ls_loner[i] = ls_loner[i] + (ls_loner[i + 2] - ls_loner[i])
					ls_loner[i + 1] = ls_loner[i + 1] + (ls_loner[i + 2] - ls_loner[i + 1])
					i += 1
					c += 2
			except:
				print(c)
				break
		else:
			print(c)
	t -= 1


def incHeights(students):
	array = list(map(int, input().split(' ')))
	array.sort(reverse=True)
	frequency = {array[0]: 1}
	for x in range(1, len(array)):
		if array[x] == array[x - 1]:
			frequency[array[x]] = frequency[array[x]] + 1
		else:
			frequency[array[x]] = 1
	loner = set()
	maxFreq = 0
	for x in frequency:
		if frequency[x] > maxFreq:
			maxFreq = frequency[x]
		if frequency[x] == 1:
			loner.add(x)
	x = len(loner)
	if x == 1:
		num = loner.pop()
		if num == max(array):
			if maxFreq > 2:
				return 1
			else:
				return 2
		else:
			return 1
	elif x % 2 == 0:
		return int(x / 2)
	else:
		return int(x / 2) + 1
for x in range(int(input())):
	students = int(input())
	if students == 0:
		print(0)
	else:
		print(incHeights(students))


import collections

def solve(p, n):
	c = collections.Counter(p)
	m = max(c)
	ans = 0
	for (i, j) in c.items():
		if j == 1:
			temp = i
			ans += 1
	if ans == 1 and m == temp:
		return 1 if any((j > 2 for j in c.values())) else min((i for i in c.values() if i != 1))
	return (ans + 1) // 2
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = solve(p, n)
	print(ans)


from collections import Counter
t = int(input())
while t:
	n = int(input())
	h = list(map(int, input().split()))
	ct = Counter(h)
	(sadkey, maxvalue, maxelem, sad) = (0, 0, 0, 0)
	for k in ct:
		v = ct[k]
		maxvalue = max(maxvalue, v)
		maxelem = max(maxelem, k)
		if v == 1:
			sad += 1
			sadkey = k
	if maxvalue == 2 and sad == 1 and (maxelem == sadkey):
		print(2)
	else:
		result = (sad + 1) // 2
		print(result)
	t -= 1


t = int(input())
for i in range(t):
	N = input()
	arr = [int(x) for x in input().split()]
	dict = {}
	for i in arr:
		dict[i] = dict.get(i, 0) + 1
	discount = 0
	for i in dict.keys():
		if dict[i] == 1:
			discount += 1
	if discount == 1:
		if dict[max(arr)] == 1:
			mini = None
			del dict[max(arr)]
			if max(dict.values()) == 2:
				print('2')
			else:
				print('1')
		else:
			print('1')
	elif discount % 2 == 0:
		print(discount // 2)
	else:
		print(discount // 2 + 1)


def fib():
	n = int(input())
	num = list(map(int, input().split()))
	d = {}
	un = 0
	for i in num:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	val = list(d.values())
	un = val.count(1)
	if d[max(num)] == 1 and un == 1:
		val.remove(1)
		if len(val) == val.count(2):
			print(2)
		else:
			print(1)
	else:
		print((un + 1) // 2)
n = int(input())
for i in range(n):
	fib()


def main():
	for _ in range(int(input())):
		N = int(input())
		arr = list(map(int, input().split()))
		dic = {}
		for i in arr:
			if i in dic.keys():
				dic[i] += 1
			else:
				dic[i] = 1
		c = 0
		f = 0
		r = 0
		for i in dic.keys():
			if dic[i] == 1:
				c += 1
				r = i
			if dic[i] > 2:
				f = 1
		if c == 1 and f == 0 and (r == max(arr)):
			print(2)
			continue
		print(c // 2 + c % 2)
main()


import sys
from sys import stdin
input = stdin.readline
import math

def li():
	return list(map(int, input().split()))

def mpi():
	return map(int, input().split())

def sli():
	return list(map(str, input().split()))

def ii():
	return int(input())

def si():
	return input()
for _ in range(ii()):
	n = ii()
	a = li()
	f = {}
	for i in a:
		if i in f:
			f[i] += 1
		else:
			f[i] = 1
	c = 0
	for (i, j) in f.items():
		if j == 1:
			c += 1
	if c == 1:
		m = max(a)
		if f[m] != 1:
			print(1)
		elif max(f.values()) > 2:
			print(1)
		else:
			print(2)
	else:
		print(math.ceil(c / 2))


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split()))
		freq = {}
		for i in range(N):
			if A[i] in freq:
				freq[A[i]] += 1
			else:
				freq[A[i]] = 1
		count = 0
		freq = sorted(list(map(lambda x: [x[0], x[1]], freq.items())), key=lambda x: x[0])
		(i, k) = (0, len(freq) - 1)
		while i < len(freq):
			if i < len(freq) - 1 and freq[i][1] == 1:
				while k > i:
					if freq[k][1] == 1:
						freq[i][1] = 0
						freq[k][1] += 1
						break
					k -= 1
				count += 1
			i += 1
		if freq[len(freq) - 1][1] == 1:
			maxFreq = 0
			for i in range(len(freq) - 1):
				maxFreq = max(maxFreq, freq[i][1])
			if maxFreq == 2:
				count += 2
			else:
				count += 1
		print(count)
main()


from collections import Counter
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	d = Counter(a)
	mi = 0
	cal = 0
	ans = 0
	for c in d:
		if d[c] == 1:
			ans += 1
			cal = c
		else:
			mi = max(mi, d[c])
	if ans == 1 and cal == max(a) and (mi == 2):
		answer = 2
	else:
		answer = int(ans / 2) + int(ans % 2)
	print(answer)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = dict()
	for i in l:
		d[i] = d.get(i, 0) + 1
	c = 0
	h = max(l)
	p = max(list(d.values()))
	for i in d:
		if d[i] == 1:
			c += 1
	if c != 0:
		x = (c + 1) // 2
		if c % 2 != 0:
			if d[h] == 1:
				if p == 2:
					x += 1
	else:
		x = 0
	print(x)


for _ in range(int(input())):
	n = int(input())
	groups = {}
	for h in map(int, input().split(' ')):
		groups[h] = groups.get(h, 0) + 1
	solos = sorted([h for (h, cnt) in groups.items() if cnt == 1], reverse=True)
	cnt = 0
	while len(solos) > 0:
		if len(solos) > 1:
			l = solos.pop(0)
			r = solos.pop(0)
			groups[l] += 1
			del groups[r]
			cnt += 1
			continue
		hsolo = solos.pop(0)
		h_gt_solo = next((h for h in groups if h > hsolo), None)
		if h_gt_solo:
			groups[h_gt_solo] += 1
			del groups[hsolo]
			cnt += 1
			continue
		(max_h, max_cnt) = max(((h, cnt) for (h, cnt) in groups.items()), key=lambda x: x[1])
		if max_cnt == 2:
			del groups[max_h]
			groups[hsolo] += 2
			cnt += 2
		else:
			groups[max_h] -= 1
			groups[hsolo] += 1
			cnt += 1
	print(cnt)


from collections import defaultdict as dd
for t in range(int(input())):
	n = int(input())
	hs = list(map(int, input().split()))
	counts = dd(int)
	for h in hs:
		counts[h] += 1
	sad = sum((v == 1 for (_, v) in counts.items()))
	if sad != 1:
		print((sad + 1) // 2)
		continue
	tallest = max(hs)
	if counts[tallest] != 1:
		print(1)
		continue
	big_group = max(counts.values())
	if big_group == 2:
		print(2)
	else:
		print(1)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	obj = {}
	ans = 0
	for i in arr:
		if i in obj:
			obj[i] += 1
		else:
			obj[i] = 1
	for (key, val) in obj.items():
		if val == 1:
			ans += 1
	if ans == 1 and arr.count(max(arr)) == 1:
		if max(obj.values()) > 2:
			print(1)
		else:
			print(2)
	else:
		print((ans + 1) // 2)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = 0
	x = Counter(l)
	y = []
	for i in x.values():
		if i == 1:
			a += 1
	if a == 1 and l.count(max(l)) == 1:
		if max(x.values()) > 2:
			print(1)
		else:
			print(2)
	else:
		print((a + 1) // 2)


from collections import Counter
tc = int(input())
for i in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	cnt = [x for x in c.values() if x == 1]
	mx = max(c.keys())
	if c[mx] == 1 and len(cnt) == 1:
		print(1 if max(c.values()) > 2 else 2)
	else:
		print(len(cnt) // 2 + len(cnt) % 2)


from collections import Counter
test = int(input())
while test != 0:
	n = int(input())
	arr = list(map(int, input().split()))
	c = Counter(arr)
	d = dict(c)
	count = 0
	for _ in c:
		if c[_] == 1:
			count += 1
	max_key = max(list(d.keys()))
	vals = list(d.values())
	if vals.count(1) == 1 and d[max_key] == 1:
		print(1 if max(vals) >= 3 else 2)
	else:
		print(count // 2 if count % 2 == 0 else count // 2 + 1)
	test -= 1


import collections
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	mh = max(h)
	mhf = h.count(mh)
	p = collections.Counter(h)
	p1 = p.values()
	f = list(p1)
	k = f.count(1)
	mg = max(f)
	if k % 2 == 1:
		ot = k // 2 + 1
		if mhf == 1:
			if mg % 2 == 0:
				ot += 1
		print(ot)
	else:
		ot = k // 2
		print(ot)


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	unique_dict = {}
	for x in arr:
		if x in unique_dict:
			unique_dict[x] += 1
		else:
			unique_dict[x] = 1
	lone_students = 0
	more_than_required = 0
	max_lone_student_height = 0
	for x in unique_dict.keys():
		if unique_dict[x] == 1:
			lone_students += 1
			max_lone_student_height = max(x, max_lone_student_height)
		if unique_dict[x] > 2:
			more_than_required += 1
	if lone_students > 1:
		print(math.ceil(lone_students / 2))
	elif lone_students == 1:
		if more_than_required > 0 or max_lone_student_height < max(arr):
			print(1)
		else:
			print(2)
	else:
		print(0)


def solve(x: list):
	m = 0
	h = {}
	for i in x:
		if i > m:
			m = i
		if i in h:
			h[i] += 1
		else:
			h[i] = 1
	s = 0
	for (k, v) in h.items():
		if v > 1:
			continue
		s += 1
	if h[m] == 1:
		h.pop(m)
		if True in map(lambda x: x == 1 or x > 2, h.values()):
			return s if s < 2 else s // 2 + 1 if s % 2 else s // 2
		else:
			return s + 1 if s < 2 else s // 2 + 2 if s % 2 else s // 2 + 1
	return s if s < 2 else s // 2 + 1 if s % 2 else s // 2
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	print(solve(x))


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	m = max(lst)
	cnt2 = lst.count(m)
	arr = []
	cnt = 1
	for i in range(len(lst) - 1):
		if lst[i] != lst[i + 1]:
			arr.append(cnt)
			cnt = 1
		else:
			cnt += 1
	if len(arr) == 0:
		arr.append(cnt)
	if lst[len(lst) - 1] == lst[len(lst) - 2]:
		arr.append(cnt)
	else:
		arr.append(1)
	cnt1 = 0
	for i in arr:
		if i == 1:
			cnt1 += 1
	if cnt2 == 1 and cnt1 == 1 and (n % 2 != 0):
		print(2)
	elif cnt1 % 2 == 0:
		print(int(cnt1 / 2))
	else:
		print(int(cnt1 / 2) + 1)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	a = max(lst)
	d = {}
	cnt1 = 0
	for j in lst:
		if j == a:
			cnt1 += 1
	for i in lst:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	cnt2 = 0
	for key in d:
		if d[key] == 1:
			cnt2 += 1
	if cnt2 == 1 and cnt1 == 1 and (n % 2 != 0):
		print(2)
	elif cnt2 % 2 == 0:
		print(int(cnt2 / 2))
	else:
		print(int(cnt2 / 2) + 1)


for _ in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	a = max(m)
	d = {}
	count1 = 0
	for j in m:
		if j == a:
			count1 += 1
	for i in m:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	count2 = 0
	for key in d:
		if d[key] == 1:
			count2 += 1
	if count2 == 1 and count1 == 1 and (n % 2 != 0):
		print(2)
	elif count2 % 2 == 0:
		print(count2 // 2)
	elif count2 % 2 != 0:
		print(count2 // 2 + 1)