Chef has an array A of length N.

Let F(A) denote the maximum frequency of any element present in the array.

For example:

If A = [1, 2, 3, 2, 2, 1], then F(A) = 3 since element 2 has the highest frequency  = 3.
If A = [1, 2, 3, 3, 2, 1], then F(A) = 2 since highest frequency of any element is 2.

Chef can perform the following operation at most once:

Choose any [subsequence] S of the array such that every element of S is the same, say x. Then, choose an integer y and replace every element in this subsequence with y.

For example, let A = [1, 2, 2, 1, 2, 2]. A few examples of the operation that Chef can perform are:
[1, \textcolor{red}{2, 2}, 1, 2, 2] \to [1, \textcolor{blue}{5, 5}, 1, 2, 2]
[1, \textcolor{red}{2}, 2, 1, \textcolor{red}{2, 2}] \to [1, \textcolor{blue}{19}, 2, 1, \textcolor{blue}{19, 19}]
[\textcolor{red}{1}, 2, 2, 1, 2, 2] \to [\textcolor{blue}{2}, 2, 2, 1, 2, 2]

Determine the minimum possible value of F(A) Chef can get by performing the given operation at most once.

------ 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 a single integer N denoting the length of array A.
- The second line contains N space-separated integers denoting the array A.

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

For each test case, output the minimum value of F(A) Chef can get if he performs the operation optimally.

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

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

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

----- Sample Output 1 ------ 
2
3
2

----- explanation 1 ------ 
Test case $1$: Chef cannot reduce the value of $F(A)$ by performing any operation.

Test case $2$: Chef can perform the operation $[\textcolor{red}{1}, 1, \textcolor{red}{1}, 1, \textcolor{red}{1}] \to [\textcolor{blue}{2}, 1, \textcolor{blue}{2}, 1, \textcolor{blue}{2}]$.
The value of $F(A)$ in this case is $3$, which is the minimum possible.

Test case $3$: Chef can perform the operation $[1, \textcolor{red}{2, 2}, 1, 2, 2] \to [1, \textcolor{blue}{5, 5}, 1, 2, 2]$. The value of $F(A)$ in this case is $2$, which is the minimum possible.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
from collections import Counter
from math import ceil, floor, gcd
for _ in range(int(input())):
	n = int(input())
	a = list(Counter([int(x) for x in input().strip().split()]).values())
	if len(a) == 1:
		print(ceil(a[0] / 2))
	else:
		a.sort()
		print(max(ceil(a[-1] / 2), a[-2]))


import math
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	fre = Counter(l)
	sfre = sorted(fre.values())
	if len(sfre) > 1:
		print(max(sfre[-2], math.ceil(sfre[-1] / 2)))
	else:
		print(math.ceil(sfre[-1] / 2))


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	kmap = {}
	for ele in arr:
		if ele not in kmap:
			kmap[ele] = 1
		else:
			kmap[ele] += 1
	maxfre = 0
	maxkey = 0
	for key in kmap:
		if kmap[key] > maxfre:
			maxkey = key
			maxfre = kmap[key]
	if maxfre % 2 == 0:
		kmap[maxkey] = maxfre // 2
	else:
		kmap[maxkey] = maxfre // 2 + 1
	maxfre = 0
	maxkey = 0
	for key in kmap:
		if kmap[key] > maxfre:
			maxkey = key
			maxfre = kmap[key]
	print(maxfre)


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	d = {}
	for a in arr:
		if a in d:
			d[a] += 1
		else:
			d[a] = 1
	freq = sorted(d.values())
	if freq[-1] % 2 == 0:
		freq[-1] = freq[-1] // 2
	else:
		freq[-1] = (freq[-1] + 1) // 2
	freq.sort()
	print(freq[-1])


t = int(input())
while t > 0:
	n = int(input())
	arr = map(int, input().split())
	d = {}
	for i in arr:
		d.setdefault(i, 0)
		d[i] += 1
	mx = 0
	minmx = 0
	for i in d.values():
		if mx < i:
			minmx = mx
			mx = i
		else:
			minmx = max(i, minmx)
	ans = (mx + 1) // 2
	if ans > minmx:
		print(ans)
	else:
		print(minmx)
	t -= 1


from collections import Counter
T = int(input())
for k in range(T):
	n = int(input())
	A = list(map(int, input().split(' ')))
	count = Counter(A)
	a = list(count.values())
	a.sort()
	p1 = 0
	if a[-1] % 2 == 0:
		a[-1] = a[-1] // 2
	else:
		a[-1] = (a[-1] + 1) // 2
	a.sort()
	print(a[-1])


import math
import statistics
from collections import Counter

def count_of_mode(arr):
	return arr.count(statistics.mode(arr))

def bp():
	return int(input())

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

def ls():
	return list(map(int, input().split()))
t = int(input())
for i in range(t):
	n = bp()
	l = ls()
	fre = Counter(l)
	sfre = sorted(fre.values())
	if len(sfre) > 1:
		print(max(sfre[-2], math.ceil(sfre[-1] / 2)))
	else:
		print(math.ceil(sfre[-1] / 2))


from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	freq = defaultdict(lambda : 0)
	mx = 0
	mv = 0
	smx = 0
	smv = 0
	for i in range(N):
		freq[A[i]] += 1
		z = freq[A[i]]
		if z > mx:
			mx = z
			mv = A[i]
		elif z > smx and mv != A[i]:
			smx = z
	z = mx // 2 + mx % 2
	print(max(z, smx))


from collections import Counter

def solve():
	n = int(input())
	A = Counter([int(i) for i in input().split()])
	if len(A) == 1:
		return (n + 1) // 2
	A = sorted(list(A.values()))
	return max(A[-2], (A[-1] + 1) // 2)
t = int(input())
while t:
	print(solve())
	t -= 1


from collections import Counter
for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	lst1 = Counter(lst)
	ans = list(lst1.values())
	ans.sort()
	if ans[-1] % 2 == 0:
		ans[-1] = ans[-1] // 2
	else:
		ans[-1] = (ans[-1] + 1) // 2
	ans.sort()
	print(ans[-1])


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = Counter(l)
	if len(d) == 1:
		print((max(d.values()) + 1) // 2)
		continue
	x = sorted(d.values())
	(fmax, fmin) = (x[-1], x[-2])
	ans = (fmax + 1) // 2
	if ans > fmin:
		print(ans)
	else:
		print(fmin)


import math
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = {}
	for num in arr:
		freq.setdefault(num, 0)
		freq[num] += 1
	(max_1, max_2) = (0, 0)
	for num in freq.values():
		if max_1 < num:
			max_2 = max_1
			max_1 = num
		else:
			max_2 = max(num, max_2)
	ans = (max_1 + 1) // 2
	if ans > max_2:
		print(ans)
	else:
		print(max_2)


from collections import Counter
t = int(input())
flag = False
num = 7
if num > 1:
	for i in range(2, num):
		if num % i == 0:
			flag = True
			break
for k in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	c = Counter(a)
	val = list(c.values())
	val.sort()
	year = 2000
	if year % 400 == 0 and year % 100 == 0:
		year = 2001
	elif year % 4 == 0 and year % 100 != 0:
		year = 2005
	else:
		year = 2020
	if val[-1] % 2 == 1:
		val[-1] = (val[-1] + 1) // 2
	else:
		val[-1] = val[-1] // 2
	if year % 400 == 0 and year % 100 == 0:
		year = 2001
	elif year % 4 == 0 and year % 100 != 0:
		year = 2005
	else:
		year = 2020
	val.sort()
	print(val[-1])


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	dict1 = {}
	for x in list1:
		if x not in dict1.keys():
			dict1[x] = 1
		else:
			dict1[x] += 1
	list2 = list(dict1.values())
	max1 = max(list2)
	if max1 % 2 == 0:
		list2.remove(max1)
		list2.append(max1 // 2)
		print(max(list2))
	else:
		list2.remove(max1)
		list2.append(max1 // 2)
		list2.append(max1 - max1 // 2)
		print(max(list2))


import math
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	xx = []
	xxx = Counter(x)
	xx = list(xxx.values())
	xx.sort()
	if len(xx) >= 2:
		print(max(math.ceil(xx[-1] / 2), xx[-2]))
	else:
		print(math.ceil(xx[-1] / 2))


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l)
	mc = c.most_common(2)
	if len(mc) == 1:
		print((mc[0][1] + 1) // 2)
		continue
	print(max(mc[1][1], (mc[0][1] + 1) // 2))


from collections import Counter
t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	c = Counter(a)
	val = list(c.values())
	val.sort()
	if val[-1] % 2 == 0:
		val[-1] = val[-1] // 2
	else:
		val[-1] = (val[-1] + 1) // 2
	val.sort()
	print(val[-1])


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = 1
		else:
			d[a[i]] += 1
	b = []
	for i in d.values():
		b.append(i)
	b.sort()
	o = len(b)
	if o == 1:
		print(math.ceil(b[0] / 2))
	else:
		c = b[-1] / 2
		if c <= max(b[0:o - 1]):
			b[-1] = b[-1] // 2
			print(max(b))
		else:
			print(math.ceil(c))


for i in range(int(input())):
	no = int(input())
	li = list(map(int, input().split()))
	dict = {}
	for i in li:
		if i in dict:
			dict[i] += 1
		else:
			dict[i] = 1
	lc = list(dict.values())
	if len(lc) == 1:
		print(len(li) // 2 + len(li) % 2)
	else:
		m1 = max(lc)
		lc.remove(m1)
		m2 = max(lc)
		print(max(m2, m1 // 2 + m1 % 2))


from collections import Counter
t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().strip().split()))[:n]
	dt = Counter(l)
	lt = list(dt.values())
	if len(lt) == 1:
		print(len(l) // 2 + len(l) % 2)
	else:
		m1 = max(lt)
		lt.remove(m1)
		m2 = max(lt)
		print(max(m2, m1 // 2 + m1 % 2))
	t -= 1


def solve(arr, n):
	mp = {}
	for i in range(n):
		if arr[i] in mp:
			mp[arr[i]] += 1
		else:
			mp[arr[i]] = 1
	freq = sorted(mp.values(), reverse=True)
	if len(freq) == 1:
		return int((freq[0] + 1) / 2)
	fir = freq[0]
	sec = freq[1]
	return max(int((fir + 1) / 2), sec)
for _ in range(int(input())):
	n = int(input())
	arr = [int(j) for j in input().split()]
	print(solve(arr, n))


for _ in range(int(input())):
	n = int(input())
	x = [int(x) for x in input().split()]
	d = {}
	for i in x:
		try:
			d[i] += 1
		except:
			d[i] = 1
	z = [d[i] for i in d if d[i] > 1]
	z.sort(reverse=True)
	if len(z) == 1:
		if z[0] % 2:
			print(z[0] // 2 + 1)
		else:
			print(z[0] // 2)
	elif len(z) == 0:
		print(1)
	else:
		if z[0] % 2:
			a = z[0] // 2 + 1
		else:
			a = z[0] // 2
		print(max(a, z[1]))


from math import ceil
listInput = lambda : list(map(int, input().split(' ')))
mapInput = lambda : map(int, input().split(' '))
for _ in range(int(input())):
	N = int(input())
	A = listInput()
	mydict = {}
	for each in A:
		if each in mydict:
			mydict[each] += 1
		else:
			mydict[each] = 1
	L = list(mydict.values())
	L.sort()
	if len(L) == 1:
		print(ceil(L[-1] / 2))
	else:
		print(max(L[-2], ceil(L[-1] / 2)))


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	k = a[0]
	b = []
	count = 1
	for j in range(1, n):
		if a[j] != k:
			b.append(count)
			count = 1
			k = a[j]
		else:
			count += 1
	b.append(count)
	b.sort(reverse=True)
	l = b[0]
	l = int(math.ceil(b[0] / 2))
	if len(b) == 1:
		print(l)
	else:
		m = b[1]
		ans = max(l, m)
		print(ans)


import collections
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	dup = set(li)
	if len(dup) == 1:
		print(-(n // -2))
		continue
	cnt = []
	for (i, c) in collections.Counter(li).items():
		cnt.append(c)
	cnt.sort()
	print(max(-(cnt[-1] // -2), cnt[-2]))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	l1 = list(d.values())
	l1.sort()
	a = l1[-1]
	b = a // 2
	c = a - b
	l1[-1] = b
	l1.append(c)
	print(max(l1))


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	hashmap = {}
	for j in arr:
		if j in hashmap:
			hashmap[j] += 1
		else:
			hashmap[j] = 1
	values = list(hashmap.values())
	maximum = 0
	maximum1 = 0
	for j in values:
		if j >= maximum:
			maximum1 = maximum
			maximum = j
		elif j > maximum1:
			maximum1 = j
	print(max(maximum1, math.ceil(maximum / 2)))


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	li = list(d.values())
	li.sort(reverse=True)
	li[0] = math.ceil(li[0] / 2)
	li.sort(reverse=True)
	print(li[0])


from collections import Counter
import math

def find(count):
	max1 = count.most_common()[0][1]
	try:
		max2 = count.most_common()[1][1]
	except:
		return math.floor((max1 + 1) / 2)
	return max(max2, math.floor((max1 + 1) / 2))
n = int(input())
for _ in range(0, n):
	m = int(input())
	array = list(map(int, input().split()))
	print(find(Counter(array)))


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = Counter(arr)
	values = list(a.values())
	values.sort()
	if values[-1] % 2 == 0:
		values[-1] = values[-1] // 2
	else:
		values[-1] = (values[-1] + 1) // 2
	values.sort()
	print(values[-1])


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	mp = list(map(int, input().split(' ')))
	cn = Counter(mp)
	flag = list(cn.values())
	flag.sort()
	if flag[-1] % 2 == 0:
		flag[-1] = flag[-1] // 2
	else:
		flag[-1] = (flag[-1] + 1) // 2
	flag.sort()
	print(flag[-1])


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	hashmap = {}
	for j in arr:
		if j in hashmap:
			hashmap[j] += 1
		else:
			hashmap[j] = 1
	values = list(hashmap.values())
	values.sort()
	if len(values) == 1:
		print(math.ceil(values[0] / 2))
	else:
		print(max(values[-2], math.ceil(values[-1] / 2)))


for _ in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	f = {}
	for i in a:
		if i in f:
			f[i] += 1
		else:
			f[i] = 1
	b = []
	for i in f:
		b.append(f[i])
	b.sort()
	if len(b) == 1:
		print((b[-1] + 1) // 2)
	elif len(b) > 1:
		if b[-1] == b[-2]:
			print(b[-1])
		elif b[-2] < (b[-1] + 1) // 2:
			print((b[-1] + 1) // 2)
		else:
			print(b[-2])


for k in range(int(input())):
	lenth = int(input())
	lst = input().split()
	d = {}
	for i in lst:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	l = sorted(d.values(), reverse=True)
	max_ = l[0]
	try:
		max_1 = l[1]
	except:
		max_1 = 0
	if max_ == lenth:
		ans = lenth // 2 if lenth % 2 == 0 else lenth // 2 + 1
	elif max_ > 2 * max_1:
		ans = max_ // 2 if max_ % 2 == 0 else max_ // 2 + 1
	else:
		ans = max_1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	d1 = {}
	for i in arr:
		if i in d1:
			d1[i] += 1
		else:
			d1[i] = 1
	temp = sorted(d1.values(), reverse=True)
	if len(d1) == 1:
		print((temp[0] + 1) // 2)
	elif temp[1] > (temp[0] + 1) // 2:
		print(temp[1])
	else:
		print((temp[0] + 1) // 2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = {}
	for i in range(n):
		if a[i] in s:
			s[a[i]] += 1
		else:
			s[a[i]] = 1
	if len(s) == 1:
		if s[a[0]] % 2 == 0:
			res = s[a[0]] // 2
		else:
			res = s[a[0]] // 2 + 1
	else:
		k = list(s.values())
		k.sort()
		(a1, b1) = (k[-1], k[-2])
		k1 = a1 // 2
		k2 = a1 - k1
		res = max(max(k1, k2), b1)
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	d = {}
	f = sf = 0
	for i in arr:
		d[i] = d.get(i, 0) + 1
		if d[i] > f:
			s = f
			f = d[i]
		elif d[i] > sf:
			sf = d[i]
	ans = max(sf, f // 2 + (1 if f % 2 != 0 else 0))
	print(ans)


import math
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = dict(Counter(l))
	p = list(d.values())
	q = list(p)
	if len(p) == 1:
		print(math.ceil(n / 2))
		continue
	p.remove(max(p))
	if math.ceil(max(q) / 2) >= max(p):
		print(math.ceil(max(q) / 2))
	else:
		print(max(p))


from collections import Counter
f = int(input())
for p in range(f):
	z = int(input())
	b = list(map(int, input().split(' ')))
	c = Counter(b)
	val = list(c.values())
	val.sort()
	if val[-1] % 2 == 0:
		val[-1] = val[-1] // 2
	else:
		val[-1] = (val[-1] + 1) // 2
	val.sort()
	print(val[-1])


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	mx = -1
	for i in d:
		mx = max(mx, d[i])
	l1 = []
	for i in d:
		l1.append(d[i])
	t = len(l1)
	l1.sort()
	if t == 1:
		if l1[0] % 2:
			print(l1[0] // 2 + 1)
		else:
			print(l1[0] // 2)
	if t > 1:
		if l1[t - 1] % 2:
			p = l1[-1] // 2 + 1
			if l1[t - 2] > p:
				print(l1[t - 2])
			else:
				print(p)
		else:
			p = l1[t - 1] // 2
			if l1[t - 2] > p:
				print(l1[t - 2])
			else:
				print(p)


from math import ceil
try:
	n = int(input())
	for j in range(n):
		a = int(input())
		l = list(map(int, input().split()))
		dit = {}
		for i in l:
			if i not in dit.keys():
				dit[i] = 1
			else:
				dit[i] += 1
		temp = []
		for i in dit.values():
			temp.append(i)
		indi = temp.index(max(temp))
		temp[indi] = ceil(temp[indi] / 2)
		print(max(temp))
except:
	pass


from math import ceil
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	l = list(d.values())
	n1 = ceil(max(l) / 2)
	l.remove(max(l))
	l = list(filter(lambda x: x >= n1, l))
	if l != []:
		print(max(l))
	else:
		print(n1)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	hashmap = {}
	for i in arr:
		if hashmap.get(i) != None:
			hashmap[i] += 1
		else:
			hashmap[i] = 1
	high = list(hashmap.values())
	high.sort(reverse=True)
	top = high[0]
	if len(high) > 1:
		print(max(high[1], (top + 1) // 2))
	else:
		print((top + 1) // 2)
	t -= 1


from collections import Counter
import math
t = int(input())
for j in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	freq = dict(Counter(arr))
	freq_arr = []
	for key in freq:
		freq_arr.append(freq[key])
	freq_arr.sort()
	n = len(freq_arr)
	if n == 1:
		print(math.ceil(freq_arr[n - 1] / 2))
		continue
	if math.ceil(freq_arr[n - 1] / 2) > freq_arr[n - 2]:
		print(math.ceil(freq_arr[n - 1] / 2))
	else:
		print(freq_arr[n - 2])


from collections import Counter
z = int(input())
for i in range(z):
	t = int(input())
	arrr = list(map(int, input().split(' ')))
	cc = Counter(arrr)
	vaaa = list(cc.values())
	vaaa.sort()
	if vaaa[-1] % 2 == 0:
		vaaa[-1] = vaaa[-1] // 2
	else:
		vaaa[-1] = (vaaa[-1] + 1) // 2
	vaaa.sort()
	print(vaaa[-1])


T = int(input())
for x in range(T):
	N = int(input())
	freq_dict = {}
	lst = list(map(int, input().split(' ')))
	for i in lst:
		if i in freq_dict:
			freq_dict[i] += 1
		else:
			freq_dict[i] = 1
	freq_lst = []
	sz = 0
	for (key, value) in freq_dict.items():
		freq_lst.append(value)
		sz += 1
	freq_lst.sort()
	max_val = freq_lst[sz - 1]
	if max_val & 1:
		max_val += 1
	max_val /= 2
	if sz == 1:
		print(int(max_val))
	else:
		print(int(max(max_val, freq_lst[sz - 2])))


from collections import Counter
t = int(input())
for k in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	cnt = Counter(arr)
	value = list(cnt.values())
	value.sort()
	if value[-1] % 2 == 0:
		value[-1] = value[-1] // 2
	else:
		value[-1] = (value[-1] + 1) // 2
	value.sort()
	print(value[-1])


t = int(input())
for i in range(t):
	n = int(input())
	x = [int(x) for x in input().split()]
	d = {}
	max1 = 0
	max2 = 0
	for i in x:
		if i not in d:
			d[i] = 1
		else:
			d[i] = d[i] + 1
		if max1 < d[i]:
			max1 = d[i]
			it = i
	for i in d:
		if i != it:
			max2 = max(max2, d[i])
	if max1 % 2 == 0:
		max1 = max1 // 2
	else:
		max1 = max1 // 2 + 1
	te = max(max1, max2)
	print(te)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	from collections import Counter
	c = Counter(a)
	d = [(i, c[i]) for i in c]
	e = [c[i] for i in c]
	d = sorted(d, key=lambda x: x[1], reverse=True)
	e = sorted(e, reverse=True)
	ans = None
	if len(d) == 1:
		ans = (len(a) + 1) // 2
	if ans == None:
		ans = max((e[0] + 1) // 2, e[1])
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dict = {}
	for i in arr:
		if i in dict.keys():
			dict[i] += 1
		else:
			dict[i] = 1
	res = list(dict.values())
	res.sort()
	if len(res) > 1:
		print(math.ceil(max(res[-1] / 2, res[-2])))
	else:
		print(math.ceil(res[-1] / 2))


import math
T = int(input())
for x in range(T):
	n = int(input())
	dict = {}
	nums = input()
	nums = nums.split(' ')
	for i in nums:
		if i in dict.keys():
			dict[i] += 1
		else:
			dict[i] = 1
	arr = []
	for i in dict.keys():
		arr.append(dict[i])
	arr.sort()
	if len(arr) == 1:
		print(int(math.ceil(arr[-1] / 2)))
	elif 2 * arr[-2] >= arr[-1]:
		print(arr[-2])
	else:
		print(int(math.ceil(arr[-1] / 2)))


t = int(input())

def mean(l):
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	t = []
	k = max(list(d.values()))
	for i in d:
		if d[i] == k:
			t.append(i)
	return (k, t)
ans = []
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	t = mean(l)
	rv = max(l) + 1
	if len(t[1]) == 1:
		if t[0] % 2:
			m = t[0] // 2 + 1
		else:
			m = t[0] // 2
		ltracker = 0
		index = 0
		temp = []
		while ltracker < m:
			if l[index] == t[1][0]:
				temp.append(rv)
				ltracker += 1
			else:
				temp.append(l[index])
			index += 1
		for j in range(index, n):
			temp.append(l[j])
		ans.append(mean(temp)[0])
	else:
		ans.append(t[0])
for i in ans:
	print(i)


from collections import Counter
for _ in range(int(input())):
	input()
	ml = list(Counter([int(s) for s in input().split()]).values())
	k = ml.index(max(ml))
	ml.append(ml[k] // 2 + ml[k] % 2)
	ml[k] //= 2
	print(max(ml))


from collections import *
tc = int(input())
for _ in range(1, 1 + tc):
	n = int(input())
	arr = list(map(int, input().split()))
	freq_dict = Counter(arr)
	freq = sorted(freq_dict.items(), key=lambda x: x[1], reverse=True)
	if len(freq) == 1:
		print(n // 2 + n % 2)
		continue
	(maxx1, maxx2) = (freq[0][1], freq[1][1])
	diff = maxx1 - maxx2
	if diff == 0:
		print(maxx1)
		continue
	if diff <= maxx2:
		print(maxx2)
	else:
		print(max(maxx1 // 2 + maxx1 % 2, maxx2))


from math import *
for i in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split(' ')))
	check = {}
	for i in numbers:
		if i not in check:
			check[i] = 1
		else:
			check[i] += 1
	check2 = list(check.values())
	max1 = max(check2)
	check2.remove(max1)
	check2 += [floor(max1 / 2), ceil(max1 / 2)]
	print(max(check2))


from collections import Counter
for tc in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	c = Counter(b)
	v = sorted(list(c.values()))
	if v[-1] % 2 == 0:
		v[-1] = v[-1] // 2
	else:
		v[-1] = (v[-1] + 1) // 2
	v.sort()
	print(v[-1])


from collections import Counter
for i in range(int(input())):
	n = int(input())
	x = 0
	y = 0
	a = list(map(int, input().split()))
	s = dict(Counter(a))
	for i in list(s):
		if s[i] > x:
			y = x
			x = s[i]
		elif s[i] > y:
			y = s[i]
	if x == y:
		print(x)
	elif x % 2 != 0 and x // 2 + 1 > y:
		print(x // 2 + 1)
	elif x % 2 == 0 and x // 2 > y:
		print(x // 2)
	else:
		print(y)


from collections import Counter
for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	y = Counter(a)
	max_val = [val for val in y.values()]
	max_val.sort()
	f = max_val[-1]
	if f == N:
		print((f + 1) // 2)
		continue
	g = max_val[-2]
	print(max((f + 1) // 2, g))


for _ in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	freq = {}
	for i in a:
		freq[i] = freq.get(i, 0) + 1
	maxVal = [val for val in freq.values()]
	maxVal.sort()
	Firsthigh = maxVal[-1]
	if Firsthigh == x:
		print((Firsthigh + 1) // 2)
		continue
	secondHigh = maxVal[-2]
	print(max((Firsthigh + 1) // 2, secondHigh))


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
	l = []
	for i in d.values():
		l.append(i)
	l.sort()
	if len(l) == 1:
		print((l[-1] + 1) // 2)
	else:
		print(max((l[-1] + 1) // 2, l[-2]))


n = int(input())
while n > 0:
	x = int(input())
	a = input()
	A = a.split(' ')
	B = []
	v = 0
	u = 0
	Dict = {}
	for i in range(0, x):
		found = 0
		if Dict.get(A[i]) == None:
			Dict[A[i]] = 1
		else:
			Dict[A[i]] = Dict[A[i]] + 1
	for item in Dict.values():
		if v <= item:
			u = v
			v = item
		elif u < item:
			u = item
	if int((v + 1) / 2) >= u:
		print(int((v + 1) / 2))
	else:
		print(u)
	n = n - 1


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	dic = {}
	for i in a:
		if dic.get(i) == None:
			dic[i] = 1
		else:
			dic[i] += 1
	arr = list(dic.values())
	arr.sort()
	arr = [0] + arr
	l = arr[-1]
	l1 = arr[-2]
	if l % 2 == 0:
		print(max(l1, l // 2))
	else:
		print(max(l1, l // 2 + 1))


def frequency(arr: list):
	arr.sort()
	_ = 1
	maxF = 0
	prevMax = 0
	counter = 0
	for i in range(len(arr) - 1):
		if arr[i] == arr[i + 1]:
			_ += 1
		else:
			if _ == maxF:
				prevMax = maxF
				counter += 1
			elif _ > maxF:
				prevMax = maxF
				maxF = _
				counter = 1
			elif _ > prevMax:
				prevMax = _
			_ = 1
	if _ == maxF:
		prevMax = maxF
		counter += 1
	elif _ > maxF:
		prevMax = maxF
		maxF = _
		counter = 1
	elif _ > prevMax:
		prevMax = _
	return [maxF, counter, prevMax]
t = int(input())
for i in range(t):
	n = input()
	arr = list(map(int, input().split(' ')))
	(f, n, prevF) = frequency(arr)
	print(f) if n > 1 else print(max(prevF, f - f // 2))


tc = int(input())
a = 0
while a < tc:
	n = int(input())
	d = dict()
	l = input()
	k = list(l.split())
	list1 = []
	count = 0
	for i in k:
		if i not in d:
			d[i] = 1
		else:
			d[i] = d[i] + 1
	vals = list(d.values())
	vals.sort()
	x = len(vals)
	if x == 1:
		if vals[-1] % 2 != 0:
			print(vals[-1] // 2 + 1)
		else:
			print(vals[-1] // 2)
	elif vals[-1] == vals[-2]:
		print(vals[-1])
	elif vals[-1] // vals[-2] < 2:
		print(vals[-2])
	elif vals[-1] // vals[-2] >= 2:
		if vals[-1] % 2 == 0:
			print(int(vals[-1] / 2))
		else:
			print(int(vals[-1] // 2 + 1))
	a = a + 1