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

Chef is given an array A consisting of N positive integers. Chef shuffles the array A and creates a new array B of length N, where B_{i} = (A_{i} + i) \bmod 2, for each i\;(1 ≤ i ≤ N).

Find the maximum possible sum of integers of the array B, if Chef shuffles the array A optimally.

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

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- Each test case contains two lines of input.
- The first line of each test case contains an integer N.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

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

For each test case, print a single line containing one integer - the maximum sum of integers of the array B.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$.

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

Subtask #1 (100 points): Original constraints

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

----- Sample Output 1 ------ 
2
3
1
----- explanation 1 ------ 
Test case $1$: One of the optimal ways to shuffle the array $A$ is $[2, 1, 3]$. Then the array $B = [(2 + 1) \bmod 2,\;(1 + 2) \bmod 2,\;(3 + 3) \bmod 2] = [1, 1, 0]$. So the sum of integers of array $B$ is $2$. There is no other possible way to shuffle array $A$ such that the sum of integers of array $B$ becomes greater than $2$.

Test case $2$: One of the optimal ways to shuffle the array $A$ is $[2, 5, 4]$. Then the array $B = [(2 + 1) \bmod 2,\;(5 + 2) \bmod 2,\;(4 + 3) \bmod 2] = [1, 1, 1]$. So the sum of integers of array $B$ is $3$ .

Difficulty: EASY
Tags: Constructive algorithms

Data structures

Mathematics

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	(e, o) = (0, 0)
	for i in l:
		if i % 2 == 0:
			e = e + 1
		else:
			o = o + 1
	(ne, no) = (0, 0)
	if n % 2 == 0:
		ne = n // 2
		no = n // 2
	else:
		ne = n // 2
		no = n // 2 + 1
	print(min(ne, o) + min(no, e))


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	even_count = 0
	odd_count = 0
	even = 0
	odd = 0
	count = 1
	for i in arr:
		if i % 2 == 0:
			even_count += 1
		else:
			odd_count += 1
		if count % 2 == 0:
			even += 1
		else:
			odd += 1
		count += 1
	e = min(odd_count, even)
	o = min(even_count, odd)
	print(o + e)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if a[i] % 2 == 0:
			count += 1
	even = n // 2
	odd = n - even
	print(min(odd, count) + min(even, n - count))


t = int(input())
for uifdshg in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	b = [0] * n
	odd = 0
	even = 0
	for i in arr:
		if i % 2:
			odd += 1
		else:
			even += 1
	if n % 2 == 0:
		oh = n // 2
		eh = n // 2
	else:
		oh = n // 2 + 1
		eh = n // 2
	o = min(even, oh)
	e = min(odd, eh)
	print(o + e)


i = int(input())
listk = []
for _ in range(i):
	p = int(input())
	st = input().split()
	st2 = []
	for ele in st:
		st2.append(int(ele))
	ev = len(st2) // 2
	if len(st2) % 2 == 1:
		ev = (len(st2) - 1) // 2
	od = len(st2) - ev
	dic1 = {}
	dic1['eve'] = 0
	dic1['odo'] = 0
	for ele in st2:
		if ele % 2 == 0:
			dic1['eve'] = dic1['eve'] + 1
		else:
			dic1['odo'] = dic1['odo'] + 1
	listk.append(min(od, dic1['eve']) + min(dic1['odo'], ev))
for ele in listk:
	print(ele)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = 0
	d = 0
	for i in b:
		if i % 2 == 0:
			c += 1
		else:
			d += 1
	if a % 2 == 0:
		e = a // 2
		f = a // 2
	else:
		e = a // 2 + 1
		f = a // 2
	k = min(c, e)
	l = min(d, f)
	print(k + l)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	o_c = 0
	e_c = 0
	for i in a:
		if i % 2 == 0:
			e_c += 1
		else:
			o_c += 1
	if n % 2 == 0:
		odd = n // 2
		even = n // 2
	else:
		even = n // 2
		odd = n // 2 + 1
	res = min(e_c + even, o_c + odd)
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(o, e) = (0, 0)
	for i in a:
		if i % 2:
			o += 1
		else:
			e += 1
	ne = n // 2
	no = n - ne
	print(min(no, e) + min(ne, o))


for _ in range(int(input())):
	n = int(input())
	l = list(sorted(map(int, input().split())))
	e_pos = n // 2
	if n % 2 == 0:
		o_pos = n // 2
	else:
		o_pos = n // 2 + 1
	o_nums = 0
	e_nums = 0
	for i in range(len(l)):
		if l[i] % 2 != 0:
			o_nums += 1
		else:
			e_nums += 1
	print(min(o_pos, e_nums) + min(e_pos, o_nums))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	even = 0
	odd = 0
	for j in A:
		if j % 2 == 0:
			even += 1
		else:
			odd += 1
	maxsum = 0
	if N % 2 == 0:
		maxsum += min(even, N // 2)
		maxsum += min(odd, N // 2)
	else:
		maxsum += min(even, N // 2 + 1)
		maxsum += min(odd, N // 2)
	print(maxsum)


t = int(input())
for t in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	even = 0
	odd = 0
	for i in a:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	odd_pos = 0
	even_pos = 0
	if n % 2 == 0:
		odd_pos = n // 2
		even_pos = n // 2
	else:
		even_pos = n // 2
		odd_pos = n // 2 + 1
	ans = min(even, odd_pos) + min(odd, even_pos)
	print(ans)


for i in range(int(input())):
	n = int(input())
	seq = list(map(int, input().split()))

	def count(list1):
		sum1 = 0
		sum2 = 0
		for i in list1:
			if i % 2 == 0:
				sum1 = sum1 + 1
			else:
				sum2 = sum2 + 1
		return [sum1, sum2]
	list1 = count(seq)
	sum1 = list1[0]
	sum2 = list1[1]
	l = 0
	if n % 2 == 0:
		if sum1 <= n / 2:
			l = n / 2 + sum1
		elif sum1 >= n / 2:
			l = n / 2 + sum2
	elif sum1 < n // 2 + 1:
		l = sum1 + n // 2
	elif sum1 > n // 2 + 1:
		l = n // 2 + 1 + sum2
	else:
		l = n
	print(int(l))


t = int(input())
for i in range(t):
	N = int(input())
	arr = [int(x) for x in input().split()]
	parity = [x % 2 for x in arr]
	pos_parity = [x % 2 for x in range(1, N + 1)]
	mismatch = 0
	type1 = 0
	type2 = 0
	for (m, n) in zip(parity, pos_parity):
		if m != n:
			mismatch += 1
		elif m == 0 and n == 0:
			type1 += 1
		elif m == 1 and n == 1:
			type2 += 1
	print(mismatch + 2 * min(type1, type2))


for _ in range(int(input())):
	p = int(input())
	a = list(map(int, input().split()))
	c_o = 0
	c_e = 0
	for i in a:
		if i % 2 == 0:
			c_e += 1
		else:
			c_o += 1
	even = odd = 0
	if p % 2 == 0:
		even = p // 2
		odd = p // 2
	else:
		even = p // 2
		odd = p // 2 + 1
	ans = min(c_o + odd, c_e + even)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	even = 0
	odd = 0
	for i in a:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if even >= odd:
		temp = even - odd
		ans = n - temp // 2
	else:
		temp = odd - even
		ans = n - temp // 2 - temp % 2
	print(ans)


t = int(input())
while t > 0:
	x = int(input())
	l = list(map(int, input().split()))
	(odd, even, final) = ([], [], [])
	for i in l:
		if i % 2 == 0:
			even.append(i)
		elif i % 2 != 0:
			odd.append(i)
	k = 0
	while len(final) < len(l):
		if k < len(even):
			final.append(even[k])
		if k < len(odd):
			final.append(odd[k])
		k += 1
	b = []
	i_value = 1
	for i in final:
		b.append((i + i_value) % 2)
		i_value += 1
	print(sum(b))
	t -= 1


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(l1, l2) = ([], [])
	c = 0
	for x in l:
		if x % 2 == 0:
			l1.append(x)
		else:
			l2.append(x)
	epos = int(n / 2)
	opos = math.ceil(n / 2)
	if len(l2) >= epos:
		c += epos
	else:
		c += len(l2)
	if len(l1) >= opos:
		c += opos
	else:
		c += len(l1)
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	e_c = 0
	o_c = 0
	k = 0
	for i in range(1, n + 1):
		if l[i - 1] % 2 == 0 and i % 2 == 0:
			e_c += 1
		elif l[i - 1] % 2 != 0 and i % 2 != 0:
			o_c += 1
		else:
			k = k + 1
	print(k + 2 * min(e_c, o_c))


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	odd = even = 0
	for i in range(n):
		if lst[i] % 2:
			odd += 1
		else:
			even += 1
	res = [0 for _ in range(n)]
	for i in range(n):
		if not i % 2:
			res[i] = 1 if even > 0 else 0
			even -= 1
		else:
			res[i] = 1 if odd > 0 else 0
			odd -= 1
	print(sum(res))


import math
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	odd = 0
	even = 0
	for i in A:
		if i % 2 == 1:
			odd += 1
		else:
			even += 1
	o = 0
	e = 0
	for i in range(N):
		if i % 2 == 1:
			o += 1
		else:
			e += 1
	if odd < even:
		o = odd
	else:
		e = even
	print(o + e)


t = int(input(''))
for z in range(t):
	n = int(input(''))
	a = list(map(int, input('').split()))[:n]
	e = 0
	for i in a:
		if i % 2 == 0:
			e += 1
	o = n - e
	if n % 2 == 0:
		print(min(o, e) + n // 2)
	elif e > o:
		print(min(o, e) + n // 2 + 1)
	else:
		print(min(o, e) + n // 2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(e, o, count) = (0, 0, 0)
	for i in l:
		if i & 1 == 1:
			e += 1
		else:
			o += 1
	if n & 1 == 1:
		count = min(n // 2 + 1, o)
		count = count + min(n // 2, e)
		print(count)
	else:
		count = min(n // 2, o)
		count = count + min(n // 2, e)
		print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	e = []
	o = []
	b = []
	for j in a:
		if j % 2 == 0:
			e.append(j)
		else:
			o.append(j)
	e.sort(reverse=True)
	o.sort(reverse=True)
	for j in range(1, n + 1):
		if j % 2 != 0:
			if len(e) != 0:
				res = (e.pop() + j) % 2
				b.append(res)
		if j % 2 == 0:
			if len(o) != 0:
				res = (o.pop() + j) % 2
				b.append(res)
	print(sum(b))


for _ in range(int(input())):
	z = int(input())
	h = list(map(int, input().split()))
	flag = tmp = 0
	for i in h:
		if i % 2 == 1:
			flag += 1
		else:
			tmp += 1
	tt = min(flag, z // 2) + min(tmp, (z + 1) // 2)
	print(tt)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = []
	arr2 = []
	arr3 = []
	arr4 = []
	for i in arr:
		if i % 2 == 0:
			arr1.append(i)
		else:
			arr2.append(i)
	while len(arr3) < n:
		if len(arr1) > 0:
			arr3.append(arr1[0])
			arr1.pop(0)
		if len(arr2) > 0:
			arr3.append(arr2[0])
			arr2.pop(0)
	for j in range(n):
		a = arr3[j] + j + 1
		arr4.append(a % 2)
	print(sum(arr4))


t = int(input())
for _ in range(0, t):
	n = int(input())
	y = list(map(int, input().split()))
	(le, lo) = (0, 0)
	for i in y:
		if i % 2 == 0:
			le += 1
		else:
			lo += 1
	ans = 0
	if lo > le:
		ans = 2 * le + (lo - le) // 2
	else:
		ans = 2 * lo + (le - lo + 1) // 2
	print(ans)


t = input()
for c in range(0, int(t)):
	n = input()
	a = input().split()
	arr = []
	for x in a:
		arr.append(int(x))
	odd = int(n) // 2 + int(n) % 2
	even = int(n) // 2
	count = 0
	for y in range(0, int(n)):
		if arr[y] % 2 == 1 and even > 0:
			count = count + 1
			even = even - 1
		elif arr[y] % 2 == 0 and odd > 0:
			count = count + 1
			odd = odd - 1
	print(count)


for x in range(int(input())):
	n = int(input())
	a = [int(d) for d in input().split()]
	even = [d for d in a if d % 2 == 0]
	odd = [d for d in a if d % 2 == 1]
	(summ, x, rem) = (0, 0, 0)
	el = len(even)
	ol = len(odd)
	if el < ol:
		x = el
		rem = 1
	else:
		x = ol
		rem = 0
	summ += 2 * x
	(o, e) = (0, 0)
	for i in range(2 * x + 1, n + 1):
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	if rem == 1:
		summ += e
	else:
		summ += o
	print(summ)


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


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	if N % 2 != 0:
		Ehave = int(N // 2) + 1
	else:
		Ehave = int(N // 2)
	Ohave = N - Ehave
	Ewant = 0
	Owant = 0
	for j in A:
		if j % 2 == 0:
			Ewant += 1
		else:
			Owant += 1
	sm = min(Ohave, Owant) + min(Ehave, Ewant)
	print(sm)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))[:n]
	e = 0
	o = 0
	for j in range(n):
		if a[j] % 2 == 1:
			o += 1
		else:
			e += 1
	if n % 2 == 1:
		m = min(o + 1, e)
		print(m + n // 2)
	else:
		m = min(o, e)
		print(int(m + n / 2))


import math
T = int(input())
for j in range(T):
	N = int(input())
	ar = list(map(int, input().split()))
	count_odd = 0
	count_even = 0
	for n in ar:
		if n % 2:
			count_odd += 1
		else:
			count_even += 1
	n_odd = math.ceil(N / 2)
	n_even = math.floor(N / 2)
	maximum_value = min(count_odd, n_even) + min(count_even, n_odd)
	print(maximum_value)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(odds, evens, nodds, nevens) = (0, 0, 0, 0)
	for i in range(n):
		if a[i] % 2 == 0:
			evens += 1
		else:
			odds += 1
		if i % 2 == 0:
			nevens += 1
		else:
			nodds += 1
	c1 = min(evens, nevens)
	c2 = min(odds, nodds)
	print(c1 + c2)


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


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	even_count = 0
	odd_coount = 0
	for i in range(n):
		if a[i] % 2 == 0:
			even_count += 1
		else:
			odd_coount += 1
	if n % 2 == 1:
		if even_count >= (n + 1) // 2:
			print((n + 1) // 2 + odd_coount)
		else:
			print(n // 2 + even_count)
	else:
		print(n // 2 + min(even_count, odd_coount))


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	lo = 0
	for item in l:
		if item & 1:
			lo += 1
	le = n - lo
	ro = n - n // 2
	re = n - ro
	if lo + ro <= n:
		print(lo + ro)
	else:
		print(n + n - lo - ro)


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

def solve(*args, **kwargs):
	(n, arr) = args
	odd = even = odd_idx = even_idx = 0
	for (idx, num) in enumerate(arr, 1):
		odd += num & 1
		even += num & 1 == 0
		odd_idx += idx & 1
		even_idx += idx & 1 == 0
	return min(odd, even_idx) + min(even, odd_idx)

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


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	flag = temp = 0
	for i in a:
		if i % 2 == 1:
			flag += 1
		else:
			temp += 1
	b = min(flag, n // 2) + min(temp, (n + 1) // 2)
	print(b)


for _ in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	(e, o, en, on) = (0, 0, 0, 0)
	if n % 2 == 0:
		o = o + n // 2
		e = e + n // 2
	else:
		o = o + n // 2 + 1
		e = e + n // 2
	for i in a:
		if i % 2 == 0:
			en += 1
		else:
			on += 1
	print(min(e, on) + min(o, en))


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	odd_places = 0
	even_places = 0
	if N % 2 == 0:
		odd_places += N // 2
		even_places += N // 2
	else:
		odd_places += N // 2 + 1
		even_places += N // 2
	odd_nos = 0
	even_nos = 0
	for j in range(N):
		if A[j] % 2 == 0:
			even_nos += 1
		else:
			odd_nos += 1
	print(min(even_nos, odd_places) + min(odd_nos, even_places))


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	flag = tmp = 0
	for i in l:
		if i % 2 == 1:
			flag += 1
		else:
			tmp += 1
	tt = min(flag, n // 2) + min(tmp, (n + 1) // 2)
	print(tt)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	want_even = 0
	want_odd = 0
	have_even = 0
	have_odd = 0
	for j in range(1, n + 1):
		if j % 2 == 0:
			want_odd += 1
		else:
			want_even += 1
		if l[j - 1] % 2 == 0:
			have_even += 1
		elif l[j - 1] % 2 != 0:
			have_odd += 1
	ans = min(want_even, have_even) + min(want_odd, have_odd)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l = []
	l1 = []
	c1 = 0
	c2 = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			c1 += 1
		if i % 2 == 0:
			c2 += 1
	l.append(c1)
	l.append(c2)
	l1.append(n - c1)
	l1.append(n - c2)
	print(min(l) + min(l1))


for tc in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = []
	ce = 0
	c = 0
	for i in range(n):
		if l[i] % 2 == 0:
			ce += 1
		if i % 2 == 0:
			c += 1
	b.append(ce)
	b.append(n - ce)
	b.append(c)
	b.append(n - c)
	print(min(b[0], b[2]) + min(b[1], b[3]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(o, e, s) = (n // 2, n // 2, 0)
	if n % 2 == 1:
		o = n // 2 + 1
	for i in l:
		if e > 0 and i % 2 == 1:
			e -= 1
			s += 1
		elif o > 0 and i % 2 == 0:
			o -= 1
			s += 1
		elif e == 0 and o == 0:
			break
	print(s)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(odd_ind, even_ind) = (0, 0)
	(c_odd, c_even) = (0, 0)
	for i in range(n):
		if i % 2 == 0:
			even_ind += 1
		elif i % 2 != 0:
			odd_ind += 1
		if l[i] % 2 == 0:
			c_even += 1
		elif l[i] % 2 != 0:
			c_odd += 1
	ans = min(even_ind, c_even) + min(odd_ind, c_odd)
	print(ans)


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


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cnt_even = cnt_odd = 0
	for i in range(n):
		if l[i] % 2 == 0:
			cnt_even += 1
		else:
			cnt_odd += 1
	even = odd = 0
	if n % 2 == 0:
		even = n // 2
		odd = n // 2
	else:
		even = n // 2
		odd = n // 2 + 1
	total = min(even + cnt_even, odd + cnt_odd)
	print(total)


t = int(input())
while t:
	n = int(input())
	e1 = n // 2
	o1 = n - n // 2
	arr = [int(i) for i in input().split()]
	e2 = 0
	for val in arr:
		if val % 2 == 0:
			e2 += 1
	o2 = n - e2
	ans = min(e1 + e2, o1 + o2)
	print(ans)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	numbers = list(map(int, input().split()))
	odd_places = int(n / 2)
	even_places = int((n + 1) / 2)
	even_numbers = 0
	odd_numbers = 0
	total = 0
	for i in numbers:
		if i % 2 == 0:
			even_numbers += 1
		else:
			odd_numbers += 1
	if odd_numbers <= odd_places:
		total += odd_numbers
	else:
		total += odd_places
	if even_numbers <= even_places:
		total += even_numbers
	else:
		total += even_places
	print(total)
	t -= 1


t = int(input())
for __ in range(t):
	n = int(input())
	(even, odd) = (0, 0)
	sum = 0
	a = list(map(int, input().split()))
	for i in range(len(a)):
		if a[i] % 2 == 0:
			even += 1
		else:
			odd += 1
	even_pos = n // 2
	if n % 2 == 1:
		odd_pos = n // 2 + 1
	else:
		odd_pos = n // 2
	sum += min(even_pos, odd)
	sum += min(odd_pos, even)
	print(sum)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = 0
	for i in range(N):
		if A[i] % 2:
			B += 1
	C = N - B
	if N % 2:
		(D, E) = (N // 2, N // 2 + 1)
		if B > D:
			print(D + C)
		elif C > E:
			print(E + B)
		else:
			print(B + C)
	else:
		(D, E) = (N // 2, N // 2)
		if B > D:
			print(D + C)
		elif C > E:
			print(E + B)
		else:
			print(B + C)


def swap(x, y):
	(arr[x], arr[y]) = (arr[y], arr[x])
tc = int(input())
while tc != 0:
	tc -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n):
		if arr[i] % 2 == 1 and i % 2 == 0:
			for j in range(i + 1, n, 2):
				if arr[j] % 2 == 0:
					swap(i, j)
					break
		if arr[i] % 2 == 0 and i % 2 == 1:
			for j in range(i + 1, n, 2):
				if arr[j] % 2 == 1:
					swap(i, j)
					break
	count = 0
	for i in range(n):
		count += (arr[i] + i + 1) % 2
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n % 2 != 0:
		eh = n // 2 + 1
	else:
		eh = n // 2
	oh = n - eh
	ow = 0
	ew = 0
	for i in l:
		if i % 2 == 0:
			ew = ew + 1
		else:
			ow = ow + 1
	print(min(ow, oh) + min(eh, ew))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(c1, c2) = (n + 1 >> 1, n >> 1)
	(c11, c22) = (0, 0)
	for i in l:
		if i % 2 != 0:
			c11 += 1
		else:
			c22 += 1
	print(min(c1, c22) + min(c2, c11))


for _ in range(int(input())):
	n = int(input())
	even = 0
	odd = 0
	l = list(map(int, input().split()))
	for i in l:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	even_index = n // 2
	odd_index = n - even_index
	print(min(even_index, odd) + min(odd_index, even))


T = int(input())
if T <= 10000 and T >= 1:
	for k in range(T):
		num_of_ints = int(input())
		str_of_int = list(map(int, input().split()))[:num_of_ints]
		(index, total, j, odd, even) = (-1, 0, 1, [], [])
		for i in range(len(str_of_int)):
			if str_of_int[i] % 2 == 1:
				odd.append(str_of_int[i])
			elif str_of_int[i] % 2 == 0:
				even.append(str_of_int[i])
		if num_of_ints % 2 == 0:
			if len(even) <= num_of_ints / 2:
				total = len(even)
				if len(odd) <= num_of_ints / 2:
					total = total + len(odd)
				else:
					total = total + num_of_ints / 2
			else:
				total = num_of_ints / 2
				if len(odd) <= num_of_ints / 2:
					total = total + len(odd)
				else:
					total = total + num_of_ints / 2
		elif len(even) <= (num_of_ints + 1) / 2:
			total = len(even)
			if len(odd) <= (num_of_ints - 1) / 2:
				total = total + len(odd)
			else:
				total = total + (num_of_ints - 1) / 2
		else:
			total = (num_of_ints + 1) / 2
			if len(odd) <= (num_of_ints - 1) / 2:
				total = total + len(odd)
			else:
				total = total + (num_of_ints - 1) / 2
		print(int(total))


for _ in range(int(input())):
	n = int(input())
	arr = [int(a) for a in input().split()]
	e = 0
	o = 0
	for l in arr:
		if l % 2 == 0:
			e = e + 1
		else:
			o = o + 1
	if n % 2 == 0:
		print(min(e, n // 2) + min(o, n // 2))
	else:
		print(min(o, n // 2) + min(e, n // 2 + 1))


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	oi = 0
	ei = 0
	o = 0
	e = 0
	for i in range(0, len(arr)):
		if arr[i] % 2:
			o += 1
		else:
			e += 1
		if i % 2:
			ei += 1
		else:
			oi += 1
	print(min(oi, e) + min(ei, o))


t = int(input())
for i in range(t):
	k = int(input())
	l = list(map(int, input().split()))
	sum = 0
	(e, o) = ([], [])
	for i in range(k):
		if l[i] % 2 == 0:
			e.append(l[i])
		else:
			o.append(l[i])
	sum += min(k // 2, len(o))
	sum += min(k - k // 2, len(e))
	print(sum)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	(o, e, c) = (0, 0, 0)
	for i in a:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	m = n // 2
	c += min(m, o)
	c += min(n - m, e)
	print(c)


try:
	for i in range(int(input())):
		temp = int(input())
		arr = list(map(int, input().split()))
		(fin_arr, a, b, f) = ([], [], [], 0)
		l = len(arr)
		for x in arr:
			if x % 2 == 0:
				a.append(x)
			else:
				b.append(x)
		q = l // 2
		p = l - q
		if len(b) > q:
			f += q
		else:
			f += len(b)
		if len(a) > p:
			f += p
		else:
			f += len(a)
		print(f)
except:
	pass