Read problem statements in [Bengali], [Russian], [Mandarin] and [Vietnamese] as well.

Naveej is from a tribe that speaks some weird language - their alphabet consists of N distinct characters.
He has an array A = [A_{1}, A_{2}, \dots, A_{N}], where A_{i} denotes the number of occurrences of the i-th character with him. 

He wants to make a [palindromic string] using all the characters he has (every character he has must be used in this string).

In order to make this possible, he can perform the following operation:
Select an i (1 ≤ i ≤ N) and convert all occurrences of i-th alphabet to any other alphabet of his choice.

Note that Naveej just wants to be able to make any palindrome, as long as every character is used. For example, if N = 2 and A = [2, 2] and we consider the characters to be a and b, he can make both abba and baab, but aba is not allowed because it uses only 3 characters.

Find the minimum number of operations required such that Naveej can make a palindromic string using all the characters he has. It can be proven that there always exists at least one sequence of operations allowing for the formation of a palindrome.

------ 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 a single integer N - the size of the alphabet.
- The second line contains N space-separated integers: A_{1}, A_{2}, ..., A_{N}, where A_{i} is the number of occurrences of the i-th character with Naveej.

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

For each test case, output a single line containing one integer - the minimum number of operations required so that Naveej can make a palindromic string using all the characters he has.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- It is guaranteed that the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

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

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

----- explanation 1 ------ 
- In the first test case, $N = 1$. Let the character be $a$. We can make the following palindromic string: $aaaa$.

- In the second test case, $N = 3$. Let the characters be $a$, $b$, $c$. It is initially not possible to make a palindrome with the given occurrences of the characters.
We perform 1 operation: 
Convert all the occurrences of $b$ to $c$.
Then, we can make the following palindromic string: $acaccaca$.

Difficulty: MEDIUM
Tags: Implementation

Starter code:

Solutions:
t = int(input())
i = 0
while i < t:
	k = []
	n = int(input())
	l = list(map(int, input().split()))
	for j in l:
		if j % 2 != 0:
			k.append(j)
	odd = len(k)
	if odd == 0:
		print(0)
	elif odd == 1:
		print(0)
	elif odd > 1 and odd % 2 == 0:
		print(odd // 2)
	elif odd > 1 and odd % 2 != 0:
		print((odd - 1) // 2)
	i += 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	y = sum(a)
	if y % 2 == 0:
		x = 0
		for j in range(n):
			if a[j] % 2 != 0:
				x += 1
		if x > 0:
			print(x // 2)
		else:
			print(x)
	else:
		x = 0
		for j in range(n):
			if a[j] % 2 != 0:
				x += 1
		if x == 1:
			print(0)
		else:
			x -= 1
			print(x // 2)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	odd = 0
	for i in l:
		if i & 1 == 1:
			odd += 1
	print(int(math.floor(odd / 2)))


t = int(input())
for i in range(t):
	n = int(input())
	l1 = [int(i) for i in input().split() if int(i) % 2 != 0]
	if l1 == []:
		print(0)
	else:
		print(len(l1) // 2)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	odd = 0
	for i in a:
		if i % 2 == 1:
			odd += 1
	print(odd // 2)


t = int(input())
for u in range(t):
	n = int(input())
	a = list(filter(lambda x: int(x) % 2, input().split()))
	m = len(a)
	print(m // 2)


for _ in range(int(input())):
	n = int(input())
	ch = [int(x) for x in input().split()]
	o = 0
	for c in ch:
		if c % 2 == 1:
			o += 1
	print(int(o / 2))


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	no_of_odd = 0
	for j in arr:
		if j % 2:
			no_of_odd += 1
	print(no_of_odd // 2)


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	odd = 0
	for j in arr:
		if j & 1:
			odd += 1
	print(odd // 2)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	for i in arr:
		if i % 2 != 0:
			c += 1
	print(c // 2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for x in a:
		if x % 2 != 0:
			ans += 1
	print(ans // 2)


import sys
for i in range(int(input())):
	n = int(input())
	a = list(map(int, sys.stdin.readline().split()))
	ans = 0
	for x in a:
		if x % 2 != 0:
			ans += 1
	print(ans // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	od = 0
	for i in range(n):
		if l[i] % 2 != 0:
			od += 1
	if sum(l) % 2 == 0:
		print(od // 2)
	else:
		print((od - 1) // 2)


T = int(input())
for i in range(0, T):
	a = int(input())
	b = input().split()
	sums = 0
	for j in b:
		sums += int(j) % 2
	print(sums // 2)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	print(len(list(filter(lambda x: x % 2 == 1, s))) // 2)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		ans = 0
	else:
		odd = 0
		for i in range(n):
			if arr[i] % 2 == 1:
				odd += 1
		ans = odd // 2
	print(ans)


n1 = int(input())
for i in range(n1):
	y = int(input())
	x = [int(a) for a in input().split()]
	c = 0
	for i in range(len(x)):
		if x[i] % 2 == 1:
			c += 1
	print(c // 2)


for t in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	odd = 0
	for i in v:
		if i % 2:
			odd += 1
	print(odd // 2)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	count = 0
	for i in arr:
		if i % 2 == 1:
			count += 1
	ans = count // 2
	print(ans)


t = int(input())
d = {}
for i in range(t):
	n = int(input())
	n1 = list(map(int, input().split()))
	count = 0
	count1 = 0
	for i in range(n):
		if n1[i] % 2 != 0:
			count += 1
		else:
			count1 += 1
	print(int(count / 2))


def f():
	n = int(input())
	pl = [int(x) for x in input().split()]
	nepar = []
	for i in pl:
		if i % 2 == 1:
			nepar.append(i)
	if len(nepar) > 1:
		return len(nepar) // 2
	return 0
t = int(input())
for i in range(t):
	print(f())


for _ in range(int(input())):
	a = int(int(input()))
	b = list(map(int, input().split()))
	c = 0
	for i in b:
		if i % 2 == 1:
			c += 1
	print(int(c / 2))


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	counte = 0
	counto = 0
	for i in range(n):
		if A[i] % 2 != 0:
			counto += 1
		else:
			counte += 1
	print(int(counto / 2))


n = int(input())
for i1 in range(n):
	n1 = int(input())
	c = c1 = c2 = 0
	l1 = [int(n1) for n1 in input().split()]
	for i in l1:
		if i % 2 != 0:
			c += 1
	if n1 == 1:
		print('0')
	else:
		print(c // 2)


n = int(input())
for i in range(n):
	n1 = int(input())
	p = p1 = p2 = 0
	l1 = [int(n1) for n1 in input().split()]
	for i in l1:
		if i % 2 != 0:
			p += 1
	if n1 == 1:
		print('0')
	else:
		print(p // 2)


n = int(input())
for i in range(n):
	n1 = int(input())
	a = a1 = a2 = 0
	l1 = [int(n1) for n1 in input().split()]
	for i in l1:
		if i % 2 != 0:
			a += 1
	if n1 == 1:
		print('0')
	else:
		print(a // 2)


t1 = int(input())
for _ in range(t1):
	num1 = int(input())
	arr = list(map(int, input().split()))
	odd = 0
	total = 0
	for num in arr:
		if num % 2 != 0:
			odd += 1
		total += num
	if num1 == 1:
		print(0)
	elif num1 == 2 and odd == 1:
		print(0)
	elif total % 2 == 0:
		print(odd // 2)
	elif total % 2 != 0:
		print((odd - 1) // 2)


t = int(input())
for _ in range(t):
	number = int(input())
	arr = list(map(int, input().split()))
	odd = 0
	total = 0
	for num in arr:
		if num % 2 != 0:
			odd += 1
		total += num
	if number == 1:
		print(0)
	elif number == 2 and odd == 1:
		print(0)
	elif total % 2 == 0:
		print(odd // 2)
	elif total % 2 != 0:
		print((odd - 1) // 2)


n = int(input())
for _ in range(n):
	a = int(input())
	lis = list(map(int, input().split()))
	if a == 1 or a == 2:
		print('0')
	else:
		c = 0
		for i in range(0, a):
			if lis[i] % 2 != 0:
				c += 1
		if c % 2 != 0:
			c = c - 1
		print(int(c / 2))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	seen_odd = False
	count = 0
	for a in arr:
		if a & 1:
			if seen_odd:
				seen_odd = False
				count += 1
			else:
				seen_odd = True
	print(count)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	if n == 1 or n == 2:
		print('0')
	else:
		for i in range(n):
			if arr[i] % 2 != 0:
				c += 1
		if c % 2 != 0:
			c = c - 1
		ans = int(c / 2)
		print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in l:
		if i % 2 != 0:
			ans += 1
	if ans == 0 or ans == 1:
		print(0)
	else:
		print(ans // 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in a:
		if i % 2 == 0:
			pass
		else:
			count += 1
	print(count // 2)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	for j in l:
		if j % 2 != 0:
			count += 1
	print(int(count / 2))


t = int(input())
while t != 0:
	n = int(input())
	x = list(map(int, input().split()))
	m = 0
	c = 0
	if n == 0:
		m = 0
		print(m)
	else:
		for i in range(n):
			if x[i] % 2 != 0:
				c = c + 1
		m = c // 2
		print(m)
	t = t - 1


for T in range(int(input())):
	N = input()
	A = list(map(int, input().split()))
	odd = 0
	for Ai in A:
		if Ai % 2 != 0:
			odd += 1
	print(odd // 2)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	c = sum([1 for i in lis if i % 2 == 1])
	print(c // 2)


T = int(input())
for _ in range(T):
	N = int(input())
	X = map(int, input().split())
	md = [x % 2 for x in X]
	print(sum(md) // 2)


import math

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	odd = list(filter(lambda x: x % 2 == 1, arr))
	if len(odd) > 1:
		x = len(odd) // 2
		return x
	return 0
for t in range(int(input())):
	print(solve())


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key as ctk
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 1000000007
sys.setrecursionlimit(100001)

def comparator(x, y):
	if x[0] == y[0]:
		return y[1] - x[1]
	return True

def ncr(n, r):
	if n < r:
		return 0
	return fc[n] * pow(fc[r] * fc[n - r] % mod, mod - 2, mod) % mod
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	sz = 0
	for i in arr:
		if i & 1:
			sz += 1
	print(sz // 2)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	arr = [int(i) for i in input().split()]
	cnt_o = 0
	cnt_e = 0
	for i in arr:
		if i % 2 == 0:
			cnt_e += 1
		else:
			cnt_o += 1
	res = 0
	if cnt_o > 1:
		res += cnt_o // 2
	print(res)


T = int(input())
for i in range(T):
	N = int(input())
	occurs = list(map(int, input().split()))
	odds = sum([occ % 2 for occ in occurs])
	print(odds // 2)


T = int(input())
for i in range(T):
	N = int(input())
	occurs = list(map(int, input().split()))
	odd_alow = N % 2
	odds = sum([occ % 2 for occ in occurs])
	fix = odds - odd_alow
	if odds % 2 == 0:
		print(odds // 2)
	else:
		print(fix // 2)