You are given an array $a$ of $n$ positive integers.

Let $\text{LIS}(a)$ denote the length of longest strictly increasing subsequence of $a$. For example,

$\text{LIS}([2, \underline{1}, 1, \underline{3}])$ = $2$.

$\text{LIS}([\underline{3}, \underline{5}, \underline{10}, \underline{20}])$ = $4$.

$\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])$ = $3$.

We define array $a'$ as the array obtained after reversing the array $a$ i.e. $a' = [a_n, a_{n-1}, \ldots , a_1]$.

The beauty of array $a$ is defined as $min(\text{LIS}(a),\text{LIS}(a'))$.

Your task is to determine the maximum possible beauty of the array $a$ if you can rearrange the array $a$ arbitrarily.


-----Input-----

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

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

The second line of each test case contains $n$ integers $a_1,a_2, \ldots ,a_n$ $(1 \leq a_i \leq 10^9)$  — the elements of the array $a$.

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 maximum possible beauty of $a$ after rearranging its elements arbitrarily.


-----Examples-----

Input
3
3
6 6 6
6
2 5 4 5 2 4
4
1 3 2 2
Output
1
3
2


-----Note-----

In the first test case, $a$ = $[6, 6, 6]$ and $a'$ = $[6, 6, 6]$. $\text{LIS}(a) = \text{LIS}(a')$ = $1$. Hence the beauty is $min(1, 1) = 1$.

In the second test case, $a$ can be rearranged to $[2, 5, 4, 5, 4, 2]$. Then $a'$ = $[2, 4, 5, 4, 5, 2]$. $\text{LIS}(a) = \text{LIS}(a') = 3$. Hence the beauty is $3$ and it can be shown that this is the maximum possible beauty.

In the third test case, $a$ can be rearranged to $[1, 2, 3, 2]$. Then $a'$ = $[2, 3, 2, 1]$. $\text{LIS}(a) = 3$, $\text{LIS}(a') = 2$. Hence the beauty is $min(3, 2) = 2$ and it can be shown that $2$ is the maximum possible beauty.

Difficulty: MEDIUM
Tags: Mathematics

Greedy algorithms

Implementation

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from collections import *
for s in [*open(0)][2::2]:
	a = Counter(s.split()).values()
	print(sum((min(2, x) for x in a)) + (1 in a) >> 1)


import sys
from collections import Counter
input = sys.stdin.readline

def beauty(numbers, n):
	if n == 1:
		return 1
	counter = Counter(numbers)
	keys = counter.keys()
	singletons = 1
	manys = 0
	for key in keys:
		if counter[key] == 1:
			singletons += 1
		else:
			manys += 1
	return manys + singletons // 2
t = int(input())
result = ''
for i in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	result += str(beauty(numbers, n))
	if i < t - 1:
		result += '\n'
print(result)


from collections import *
for s in [*open(0)][2::2]:
	c = Counter(s.split())
	print(sum((min(2, c[x]) for x in c)) + 1 >> 1)


import sys

def mingidit(i):
	digits = list(str(i))
	if len(digits) == 2:
		return int(digits[-1])
	return int(min(digits))

def ZXC(a, b, c):
	return [a + b + c, c + b, c]
from collections import Counter

def LIS(li):
	c = Counter(li)
	cl = c.values()
	m = len([x for x in cl if x > 1])
	s = len(cl) - m
	if s % 2 == 0:
		return m + int(s / 2)
	else:
		return m + int(s / 2) + 1
r = int(sys.stdin.readline())
for j in range(r):
	kk = sys.stdin.readline()
	li = [int(x) for x in sys.stdin.readline().split()]
	print(LIS(li))


def main():
	t = int(input())
	while t:
		n = int(input())
		arr = [int(x) for x in input().split()]
		arrMap = {}
		for i in arr:
			if i in arrMap.keys():
				arrMap[i] += 1
			else:
				arrMap[i] = 1
		doubles = 0
		singles = 0
		for i in arrMap.keys():
			if arrMap[i] > 1:
				doubles += 1
			else:
				singles += 1
		if singles % 2 == 0:
			print(doubles + singles // 2)
		else:
			print(doubles + singles // 2 + 1)
		t -= 1
	return 0
main()


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	c1 = 0
	c2 = 0
	d = dict()
	for i in map(int, inp().split()):
		v = d.get(i, 0)
		if v == 1:
			c1 -= 1
			c2 += 1
		elif v == 0:
			c1 += 1
		d[i] = v + 1
	r = 0
	if c1 > 0:
		c1 -= 1
		r += 1
	elif c2 > 0:
		c2 -= 1
		r += 1
	r += c2 + c1 // 2
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import math
n = int(input())
for k in range(n):
	nk = int(input())
	arr = list(map(int, input().split()))
	if len(arr) == 1:
		print(1)
		continue
	nums = {}
	nums2 = {}
	lis1 = 0
	lis2 = 0
	for el in arr:
		if el not in nums:
			nums[el] = 1
			lis1 += 1
		elif el not in nums2:
			nums2[el] = 1
			lis2 += 1
	ans = math.ceil((lis1 + lis2) / 2)
	print(ans)


from collections import Counter

def main():
	tc = int(input())
	for _ in range(tc):
		n = int(input())
		arr = [int(a) for a in input().split()]
		cntr = Counter(arr)
		(cnt1, cnt2) = (0, 0)
		for val in cntr.values():
			if val >= 2:
				cnt1 += 1
			else:
				cnt2 += 1
		print(cnt1 + (cnt2 + 1) // 2)
main()


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = {}
	for i in range(n):
		if arr[i] not in cnt:
			cnt[arr[i]] = 0
		cnt[arr[i]] += 1
	single = ans = 0
	for key in cnt:
		if cnt[key] >= 2:
			ans += 1
		else:
			single += 1
	return ans + (single + 1) // 2
for _ in range(int(input())):
	print(solve())


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	if n == 1:
		print(1)
		return
	net = collections.Counter(A)
	(one, two) = (0, 0)
	for i in net.values():
		if i > 1:
			two += 1
		else:
			one += 1
	ans = two + ceil(one / 2)
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


def resii():
	n = int(input())
	a = list(map(int, input().split()))
	m = {}
	for a_i in a:
		m[a_i] = m.get(a_i, 0) + 1
	iz = 0
	for v in m.values():
		iz += min(2, v)
	print((iz + 1) // 2)
for _ in range(int(input())):
	resii()


inputs = []
import math
for i in range(int(input())):
	input()
	inputs.append(list(map(int, input().split(' '))))
for inp in inputs:
	counts = {}
	for x in inp:
		if x in counts:
			counts[x] += 1
		else:
			counts[x] = 1
	sum_ = 0
	for val in counts.values():
		sum_ += val if val <= 2 else 2
	print(math.ceil(sum_ / 2))


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cnt = Counter(l)
	d = dict(cnt)
	a = 0
	b = 0
	for (k, v) in d.items():
		if v == 1:
			b += 1
		else:
			a += 1
	print(a + (b + 1) // 2)


for i in range(int(input())):
	n = input()
	d = {}
	for j in list(map(int, input().split())):
		d[j] = d.get(j, 0) + 1
	ans = 1
	for j in d:
		ans += min(2, d[j])
	print(ans // 2)


from collections import defaultdict

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	m = defaultdict(int)
	for i in range(n):
		m[a[i]] += 1
	(s, d) = (0, 0)
	for v in m.values():
		if v == 1:
			s += 1
		if v > 1:
			d += 1
	print(d + (s + 1) // 2)
t = int(input())
for _ in range(t):
	solve()


from collections import Counter

def main():
	n = int(input())
	for _ in range(n):
		input()
		s = input()
		print(solve(s))

def solve(s):
	counter = Counter((int(num_str) for num_str in s.split()))
	two_or_more = 0
	single = 0
	for (num, count) in counter.items():
		if count >= 2:
			two_or_more += 1
		else:
			single += 1
	return two_or_more + (single - single // 2)
main()


times = int(input())
for time in range(times):
	n = int(input())
	nums = map(int, input().split())
	ones = set()
	twos = set()
	for j in nums:
		if j in twos:
			continue
		if j in ones:
			twos.add(j)
			continue
		ones.add(j)
	out = len(ones) + len(twos)
	if len(twos) < len(ones):
		out += 1
	print(out // 2)


import sys
input = lambda : sys.stdin.readline().strip()
for Homu in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	counts = {}
	for x in l:
		if x in counts:
			counts[x] += 1
		else:
			counts[x] = 1
	solo = 0
	dupe = 0
	for i in counts:
		if counts[i] == 1:
			solo += 1
		else:
			dupe += 1
	if solo > 0:
		solo -= 1
		dupe += 1
	ans = solo // 2 + dupe
	print(ans)


import math
t = int(input())
for _ 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
	nonrep = 0
	rep = 0
	for k in d:
		if d[k] > 1:
			rep += 1
		else:
			nonrep += 1
	ans = math.ceil(nonrep / 2) + rep
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	counts = {}
	for i in arr:
		if i in counts:
			counts[i] += 1
		else:
			counts[i] = 1
	count = 0
	for i in counts:
		count += min(2, counts[i])
	if count % 2 == 1:
		print((count + 1) // 2)
	else:
		print(count // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	d = {}
	for x in a:
		d[x] = d.get(x, 0) + 1
	count = 0
	for v in d.values():
		if v > 1:
			count += 1
	n = len(d)
	if n == count:
		print(n)
	else:
		count += 1
		print(count + (n - count) // 2)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n,) = map(int, input().split())
	a = list(map(int, input().split()))
	c = defaultdict(int)
	for i in a:
		c[i] += 1
	s = 0
	m = 0
	for i in c:
		if c[i] == 1:
			s += 1
		elif c[i] > 1:
			m += 1
	ans = 0
	if s % 2 != 0:
		ans += 1
		s -= 1
	ans += m + s // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dict = {}
	for i in range(n):
		if a[i] in dict:
			dict[a[i]] += 1
		else:
			dict[a[i]] = 1
	count = 0
	for i in dict:
		if dict[i] >= 2:
			count += dict[i] - 2
	p = n - count
	print(p // 2 + p % 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	kekw = {}
	ans = 0
	ans2 = 0
	for i in a:
		try:
			kekw[i] += 1
		except:
			kekw[i] = 1
	for i in kekw:
		if kekw[i] == 1:
			ans2 += 1
	ans = (ans2 + 1) // 2 + (len(kekw) - ans2)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = {}
	for i in range(n):
		if arr[i] in freq:
			freq[arr[i]] += 1
		else:
			freq[arr[i]] = 1
	(t, s) = (0, 0)
	for (key, value) in freq.items():
		if value >= 2:
			t += 1
		else:
			s += 1
	print(t + (s + 1) // 2)


import sys
from collections import Counter
from math import ceil
sys.setrecursionlimit(10 ** 5)

def pro(arr):
	n = len(arr)
	dic = {}
	for i in range(n):
		dic[arr[i]] = dic.get(arr[i], 0) + 1
	(a, b) = (0, 0)
	for (i, j) in dic.items():
		if j >= 2:
			b += 1
		else:
			a += 1
	print(b + ceil(a / 2))
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	pro(arr)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = {}
	for e in a:
		if e not in m:
			m[e] = 1
		else:
			m[e] += 1
	dbl = 0
	sgl = 0
	for e in m:
		if m[e] >= 2:
			dbl += 1
		else:
			sgl += 1
	print(dbl + ceil(sgl / 2))


from collections import Counter
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split(' ')))
	count = 0
	ans = 0
	h = Counter(a)
	for i in h:
		if h[i] >= 2:
			ans += 1
		else:
			count += 1
	if count > 0:
		ans += 1
		count -= 1
	ans += count // 2
	print(ans)
	t -= 1


from collections import Counter

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = Counter(a)
	s = 0
	l1 = len(c)
	for i in c:
		if c[i] > 1:
			s += 1
	if s != l1:
		s += 1
	l2 = s + (l1 - s) // 2
	print(l2)
for _ in range(int(input())):
	solve()


from collections import Counter
n = int(input())

def lis_lds(arr):
	cnt = 0
	f1 = 0
	arr_counter = Counter(arr)
	for item in arr_counter:
		if arr_counter[item] >= 2:
			cnt += 1
		else:
			f1 += 1
	print(cnt + (f1 + 1) // 2)
for _ in range(n):
	l = int(input())
	lis_lds([*map(int, input().split())])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	di = {}
	z = 0
	for x in l:
		if x not in di:
			di[x] = 1
		else:
			di[x] += 1
	for x in di:
		if di[x] >= 2:
			z += 2
		else:
			z += 1
	print((z + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	h = {}
	ans = 0
	for x in l:
		if x not in h:
			h[x] = 1
		else:
			h[x] += 1
	for x in h:
		if h[x] >= 2:
			ans += 2
		else:
			ans += 1
	print((ans + 1) // 2)


t = int(input())
for ii 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
	c1 = 0
	c2 = 0
	for i in d.values():
		if i > 1:
			c1 += 1
		else:
			c2 += 1
	ans = int(c2 / 2) + c2 % 2
	print(ans + c1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = True
	d = {}
	for i in arr:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	count = 0
	for i in d.keys():
		if d[i] == 1:
			if flag:
				count += 1
				flag = False
			else:
				flag = True
		if d[i] >= 2:
			count += 1
	print(count)


from functools import lru_cache
from copy import deepcopy
import math
import sys
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
test_case = 1
test_case = int(input())

def ans():
	n = cin()
	arr = ari()
	lst = set(arr)
	x = len(lst)
	best = math.ceil(x / 2)
	dito = {}
	for i in arr:
		if i not in dito:
			dito[i] = 1
		else:
			dito[i] += 1
	bestcount = 0
	cola = 0
	mac = max(arr)
	for (k, v) in dito.items():
		if v > 1:
			cola += 1
		else:
			bestcount += 1
	local = min(x, bestcount)
	return cola + (bestcount + 1) // 2
for _ in range(test_case):
	print(ans())


for i in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	dict = {}
	for j in ls:
		dict[j] = dict.get(j, 0) + 1
	cnt = 0
	for j in dict.values():
		cnt += min(2, j)
	print((cnt + 1) // 2)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	dic = {}
	c = 0
	r = n
	for i in range(n):
		if l[i] in dic:
			dic[l[i]] += 1
		else:
			dic[l[i]] = 1
	for key in dic.keys():
		if dic[key] > 1:
			r -= dic[key]
			c += 1
	if r % 2 == 1:
		print(c + (r + 1) // 2)
	else:
		print(c + r // 2)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = {}
	for a_i in a:
		m[a_i] = m.get(a_i, 0) + 1
	z = 1
	for v in m.values():
		z += min(2, v)
	print(z // 2)


def main():
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for a in l:
		d.setdefault(a, 0)
		d[a] += 1
	u = 0
	for a in d:
		u += min(d[a], 2)
	return (u + 1) // 2
t = int(input())
for _ in range(t):
	print(main())


import collections
import math
for i in range(int(input())):
	n = n = int(input())
	l = list(map(int, input().split()))
	l2 = set(l)
	n2 = len(l2)
	tot = 0
	tot2 = 0
	if n2 > 1:
		dic = collections.Counter(l)
		for h in dic:
			if dic[h] > 1:
				tot2 += 1
			elif dic[h] == 1:
				tot += 1
		print(tot2 + math.ceil(tot / 2))
	else:
		print(1)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	arr = [int(x) for x in input().split()]
	mx = max(arr)
	for i in arr:
		d[i] += 1
	(one, two) = (0, 0)
	for (key, value) in d.items():
		if value == 1:
			one += 1
		else:
			two += 1
	ans = two
	if one & 1:
		one += 1
	ans += one >> 1
	print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	t = [int(x) for x in input().split()]
	x = Counter(t)
	for g in x.keys():
		n -= max(0, x[g] - 2)
	print((n + 1) // 2)


class Solution:

	def solve(self, n, a):
		if n == 1:
			return 1
		nums = {}
		for i in a:
			if i in nums.keys():
				nums[i] += 1
			else:
				nums[i] = 1
		single = 0
		double = 0
		for num in nums.keys():
			if nums[num] >= 2:
				double += 1
			else:
				single += 1
		result = double
		if single // 2 == single / 2:
			result += single // 2
		else:
			result += single // 2 + 1
		return result
T = int(input())
while T:
	T -= 1
	n = int(input())
	a = list(map(int, input().split()))
	print(Solution().solve(n, a))


import collections
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = collections.Counter(a)
	ans1 = ans2 = 0
	for i in d.keys():
		if d[i] > 1:
			ans1 += 1
		else:
			ans2 += 1
	print(ans1 + (ans2 + 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	dic = {}
	for j in lst:
		dic[j] = 0
	for j in lst:
		dic[j] += 1
	c = 0
	for j in dic.keys():
		if dic[j] == 1:
			c += 1
	ans = 0
	l = 0
	for j in dic.keys():
		if dic[j] > 1:
			l += 1
	if c % 2 == 0:
		ans += c // 2
	else:
		ans += c // 2 + 1
	ans += l
	print(ans)


import sys
from collections import deque, Counter
input = lambda : sys.stdin.readline().strip()
intput = lambda : map(int, input().split())

def solve():
	(N,) = intput()
	A = [*intput()]
	cnt = Counter(A)
	c = sorted(cnt)
	L = R = 0
	for x in c:
		if cnt[x] == 1:
			(L := (L + 1)) if L < R else (R := (R + 1))
		else:
			(L, R) = (L + 1, R + 1)
	if L < R:
		L += 1
	return min(L, R)
(T,) = intput()
for _ in range(T):
	print(solve())


c = int(input())
for i in range(c):
	sc = int(input())
	s = input().split()
	s.sort()
	res = sc
	for i in range(2, sc, 1):
		if s[i] == s[i - 1] and s[i] == s[i - 2]:
			res -= 1
	if res % 2 == 0:
		print(int(res / 2))
	else:
		print(int(res / 2) + 1)


t = int(input())
while t:
	n = int(input())
	A = [int(i) for i in input().split()]
	d = dict()
	for i in range(n):
		d[A[i]] = d.get(A[i], 0) + 1
	res = 0
	for i in d:
		if d[i] > 2:
			res += 2
		else:
			res += d[i]
	print((res + 1) // 2)
	t -= 1


t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = {}
	for ele in a:
		if ele in b:
			b[ele] += 1
		else:
			b[ele] = 1
	count = num = 0
	for ele in b.values():
		if ele >= 2:
			count += 1
		else:
			num += 1
	if num % 2 == 0:
		print(num // 2 + count)
	else:
		print(num // 2 + 1 + count)


from math import ceil
from sys import stdin
input = stdin.readline
from collections import Counter

def f(a):
	one = set()
	two = set()
	if len(a) == 1:
		return 1
	cnt = Counter(a)
	for i in cnt:
		if cnt[i]:
			cnt[i] -= 1
			one.add(i)
		if cnt[i]:
			two.add(i)
	return ceil((len(one) + len(two)) / 2)
for _ in range(int(input())):
	n = input()
	a = [*map(int, input().strip().split())]
	print(f(a))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	cnt = 1
	for i in range(n):
		if i < 2 or a[i] != a[i - 2]:
			cnt += 1
	print(cnt // 2)


def beautyOfArray(arr, n):
	mylist = sorted(arr)
	count = 1
	for i in range(n):
		if i < 2 or mylist[i] != mylist[i - 2]:
			count = count + 1
	return count // 2
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	beauty = beautyOfArray(arr, n)
	print(beauty)
	t = t - 1


from posixpath import split
for t in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	c = 0
	dic = {}
	for i in L:
		try:
			dic[i] += 1
			dic[i] = 2
		except:
			dic[i] = 1
	for (i, j) in dic.items():
		c += j
	print((c + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	from collections import Counter
	arr = Counter(arr)
	two = sum((1 for (k, v) in arr.items() if v > 1))
	one = len(arr) - two
	res = two + (1 if one else 0) + ((one - 1) // 2 if one else 0)
	print(res)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	(f, b, bb) = ([], [], set())
	for i in range(n):
		if not f:
			f.append(arr[i])
		elif not b:
			b.append(arr[i])
			bb.add(arr[i])
		elif len(f) == len(b):
			if f[-1] < arr[i]:
				f.append(arr[i])
		elif b[-1] < arr[i]:
			b.append(arr[i])
	return max(len(f), len(b))
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	from collections import Counter
	c = Counter(a)
	t = 0
	s = 0
	for i in c:
		if c[i] >= 2:
			t += 1
		else:
			s += 1
	if s // 2 == s / 2:
		print(t + s // 2)
	else:
		print(t + s // 2 + 1)


from collections import Counter

def solve():
	n = int(input())
	a = sorted(map(int, input().split()))
	c = Counter(a)
	l1 = len(c)
	s = sum((c[i] > 1 for i in c))
	if s != l1:
		s += 1
	l2 = s + (l1 - s) // 2
	print(l2)
for _ in range(int(input())):
	solve()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	print(sum((x >= 2 for x in c.values())) + sum((x == 1 for x in c.values())) // 2 + sum((x == 1 for x in c.values())) % 2)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	i = 0
	(ans, d) = (0, 0)
	e = False
	while i < n:
		s = i
		x = 0
		while i < n and a[i] == a[s]:
			i += 1
			x += 1
		if x >= 2:
			ans += 1
		else:
			e = True
			if d != 0:
				d = 0
			else:
				d += 1
				ans += 1
	if e:
		print(ans)
	else:
		print(ans - d)
for _ in range(int(input())):
	main()


for _ in range(int(input())):
	n = int(input())
	a = list(sorted(map(int, input().split())))
	cnt = dict()
	for i in range(n):
		if a[i] not in cnt:
			cnt[a[i]] = 1
		else:
			cnt[a[i]] += 1
	s = 0
	t = 0
	for u in cnt:
		if cnt[u] >= 2:
			t += 1
		else:
			s += 1
	print(t + (s + 1) // 2)


import math
for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	a = set(A)
	if n == 1:
		print(1)
	elif len(a) == n:
		if n % 2 == 1:
			print(n // 2 + 1)
		else:
			print(n // 2)
	else:
		d = dict()
		for j in range(n):
			if A[j] not in d:
				d[A[j]] = 1
			else:
				d[A[j]] += 1
		m = []
		o = []
		for k in d:
			if d[k] > 1:
				m.append(k)
			else:
				o.append(k)
		if len(o) % 2 == 0:
			print(len(m) + len(o) // 2)
		else:
			print(len(m) + len(o) // 2 + 1)


import math
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if s[i] not in d:
			d[s[i]] = 0
		d[s[i]] += 1
	(p, q) = (0, 0)
	for i in d.keys():
		if d[i] == 1:
			p += 1
		else:
			q += 1
	print(math.ceil(q + p / 2))


i = input()
for a in range(0, int(i)):
	input()
	arr = [int(x) for x in input().split()]
	arr.sort()
	total = 0
	size = 1
	e = arr[0]
	for n in arr[1:]:
		if n == e:
			size += 1
		else:
			total += min(2, size)
			e = n
			size = 1
	total += min(2, size)
	r = int(total // 2) + total % 2
	print(r)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	d = {}
	for i in range(n):
		if l[i] not in d:
			d[l[i]] = 1
		else:
			d[l[i]] += 1
	c = 0
	ans = 0
	for i in d:
		if d[i] > 1:
			ans += 1
		else:
			c += 1
	print(ans + math.ceil(c / 2))


from math import ceil
T = int(input())
for t in range(T):
	n = int(input())
	s = list(map(int, input().split()))
	dd = {x: 0 for x in set(s)}
	drl = 0
	for x in s:
		dd[x] += 1
		if dd[x] <= 2:
			drl += 1
	print(ceil(drl / 2))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l)
	if n == 1:
		print(1)
	else:
		d = {}
		for i in l:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		ans = 0
		ones = 0
		for i in d:
			if d[i] > 1:
				ans += 1
			else:
				ones += 1
		if ones % 2 == 0:
			ans += ones // 2
			print(ans)
		else:
			ans += ones // 2 + 1
			print(ans)


def lis(our_list):
	our_dict = {}
	B = []
	for el in our_list:
		if el in our_dict:
			our_dict[el] += 1
		else:
			our_dict[el] = 1
			B.append(el)
	B.sort(key=lambda x: our_dict[x])
	counter1 = 1
	for i in range(1, len(B)):
		x = B[i]
		if our_dict[x] == 1:
			counter1 += 0.5
		else:
			counter1 += 1
	return int(counter1 * 2 // 2)
t = int(input())
for i in range(t):
	n = input()
	print(lis(list(map(int, input().split()))))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = set(arr)
	d = {}
	for x in s:
		d[x] = 0
	for x in arr:
		d[x] += 1
	mele = max(arr)
	ne = 0
	for (k, v) in d.items():
		if k != mele:
			ne += min(v, 2)
	if d[mele] == 1:
		print(ne // 2 + 1)
	else:
		print(math.ceil(ne / 2) + 1)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = list(map(int, input().split()))
	m = dict()
	for i in range(n):
		if s[i] not in m:
			m[s[i]] = 0
		m[s[i]] += 1
	ans = 0
	c2 = 0
	c1 = 0
	for x in m:
		if m[x] >= 2:
			c2 += 1
		elif m[x] == 1:
			c1 += 1
	print((c1 + 1) // 2 + c2)


import math
import bisect

def printf(str):
	print(str, end=' ')
test_case = int(input())
t = 0
while t < test_case:
	t += 1
	input()
	arr = [int(x) for x in input().split()]
	arr.sort()
	total = 0
	size = 1
	e = arr[0]
	for n in arr[1:]:
		if n == e:
			size += 1
		else:
			total += min(2, size)
			e = n
			size = 1
	total += min(2, size)
	r = int(total // 2) + total % 2
	print(r)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split())))
	A.sort()
	X = {}
	for i in A:
		X[i] = X.get(i, 0) + 1
	X = list(X.values())
	ans = 0
	flag = 1
	for i in X:
		if i > 2:
			ans += 2
			flag = 1
		else:
			ans += i
	print((ans + 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 1
	a.sort()
	for j in range(n):
		if j < 2 or a[j] != a[j - 2]:
			c += 1
	print(c // 2)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n == 1:
		print(1)
	else:
		arr = sorted(arr)
		itr1 = [arr[i] for i in range(0, n, 2)]
		itr2 = [arr[i] for i in range(1, n, 2)]
		x1 = len(set(itr1))
		x2 = len(set(itr2))
		print((x1 + x2 + 1) // 2)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = Counter(a)
	s = sorted(d)
	count = 0
	for i in s:
		if d[i] >= 2:
			count += 1
		else:
			count += 1 / 2
	if count > int(count):
		count = 1 + int(count)
	else:
		count = int(count)
	print(count)


import math
from collections import Counter
for i in range(int(input())):
	lenn = int(input())
	list1 = list(map(int, input().split()))
	if lenn == 1:
		print(1)
	else:
		list1.sort()
		d = dict(Counter(list1))
		imp = list(d.values())
		ans = 0
		for i in imp:
			ans += min(2, i)
		print(math.ceil(ans / 2))


inputs = []
for i in range(int(input())):
	input()
	inputs.append(list(map(int, input().split(' '))))
for inp in inputs:
	list_ = list(sorted(inp))
	list1 = [list_[0]]
	count = 0
	for i in range(1, len(list_)):
		a = list_[i]
		if a == list_[i - 1] and count < 1:
			count += 1
			list1.append(a)
		elif a != list_[i - 1]:
			list1.append(a)
			count = 0
	if len(list1) % 2 == 0:
		print(len(list1) // 2)
	else:
		print((len(list1) + 1) // 2)


import collections
t = int(input())
while t > 0:
	n = int(input())
	a = input().split()
	d = collections.defaultdict(int)
	for i in range(n):
		a[i] = int(a[i])
		d[a[i]] += 1
	ex = 0
	for i in range(n):
		if d[a[i]] > 2:
			ex += d[a[i]] - 2
			d[a[i]] = 0
	l = n - ex
	print(l // 2 + l % 2)
	t -= 1


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(int)
	m = 0
	for i in a:
		d[i] += 1
		m = max(m, i)
	x = y = 0
	p = 1
	for i in d:
		if d[i] == 1 and p:
			x += 1
			y += 1
			p = 0
		elif d[i] == 1:
			if x < y:
				x += 1
			else:
				y += 1
		else:
			x += 1
			y += 1
	print(min(x, y))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ind = [1]
	for j in range(1, len(a)):
		if a[j] == a[j - 1] and ind[len(ind) - 1] == 1:
			ind[len(ind) - 1] += 1
		elif a[j] != a[j - 1]:
			ind.append(1)
	c2 = 0
	c1 = 0
	for j in range(len(ind)):
		if ind[j] == 2:
			c2 += 1
		else:
			c1 += 1
	print(c2 + c1 // 2 + c1 % 2)


T = int(input())
for t in range(T):
	length = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	i = 0
	ans = length
	while i < length:
		nxt = i
		cnt = 0
		while nxt < length and arr[nxt] == arr[i]:
			cnt += 1
			nxt += 1
		if cnt >= 3:
			ans -= cnt - 2
		i = nxt
	print(int((ans + 1) / 2))


from collections import Counter
n = int(input())
for _ in range(n):
	count = int(input())
	a = list(map(int, input().split()))
	a.sort()
	d = Counter(a)
	up = []
	down = []
	flag = 0
	max_ = max(a)
	for i in d.keys():
		if d[i] >= 2:
			up.append(i)
			down.append(i)
		elif not flag:
			down.append(i)
			up.append(i)
			flag = 1
		elif len(up) >= len(down):
			down.append(i)
		else:
			up.append(i)
	len_up = len(up)
	len_down = len(down)
	print(min(len_up, len_down))