Chef has an array A of length N. In one operation, Chef can choose any element A_{i} and split it into two positive integers X and Y such that X+Y = A_{i}.  
Note that the length of array increases by 1 after every operation.

Determine the minimum numbers of operations required by Chef to make [parity] of all the elements same.

It is guaranteed that parity of all the elements can be made equal after applying the above operation zero or more times.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N — the length of array A.
- Next line contains N space-separated integers A_{1}, A_{2}, A_{3}, \dots, A_{N} - denoting the array A.

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

For each test case, output the minimum number of operations required to make parity of all elements same.

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

$1 ≤ T ≤ 4000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ does not exceed $2 \cdot 10^{5}$

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

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

----- explanation 1 ------ 
Test case $1$: All the elements have the same parity since all are odd. Thus, we need zero operations.

Test case $2$: In one operation, we can split the element $A_{2} = 2$ to $X = 1$ and $Y = 1$ such that $X+Y = 2$. Thus, the array now becomes $A = [1, 1, 1, 3]$. All the elements have the same parity since all are odd. Thus, we need only one operation.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	a = list(map(int, input().split()))
	a1 = len(a)
	for i in a:
		if i % 2 == 0:
			count = count + 1
	if count == a1 or count == 0:
		print(0)
	else:
		print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	integers = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if integers[i] % 2 == 0:
			count += 1
	if count == 0 or count == n:
		print(0)
	else:
		print(count)


for _ in range(int(input())):
	n = int(input())
	a = list((x % 2 for x in map(int, input().split())))
	odd = sum(a)
	even = n - odd
	print(0 if even == n else even)


cases = int(input())
for i in range(cases):
	size = int(input())
	list1 = [int(x) for x in input().split()]
	even_count = len(list(filter(lambda x: x % 2 == 0, list1)))
	if even_count == size:
		print('0')
	else:
		print(even_count)


t = int(input())
while 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 odd == 0:
		print(0)
	elif odd > 0:
		print(even)
	t -= 1


def make_parity_equal(A):
	E = sum((1 for x in A if x % 2 == 0))
	O = sum((1 for x in A if x % 2 != 0))
	if E == len(A) or O == len(A):
		return 0
	else:
		return E
for i in range(int(input())):
	n = int(int(input()))
	a = list(map(int, input().split()))
	print(make_parity_equal(a))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	e = o = 0
	for i in a:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	if e == 0 or o == 0:
		print(0)
	else:
		print(e)


n = int(input())
for i in range(n):
	w = int(input())
	a = list(map(int, input().split()))
	odd = 0
	even = 0
	for j in a:
		if j % 2 == 1:
			odd = odd + 1
		else:
			even = even + 1
	if odd == 0 or odd == w:
		print('0')
	else:
		print(even)


test_case = int(input())
for i in range(test_case):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for j in range(n):
		if arr[j] % 2 == 0:
			count += 1
	if count == n:
		print(0)
	else:
		print(count)


n = int(input())
while n:
	t = int(input())
	ip1 = input().split()
	l1 = [int(i) for i in ip1]
	count = 0
	for i in range(0, t):
		if l1[i] % 2 == 0:
			count += 1
	if count == t or count == 0:
		print(0)
	else:
		print(count)
	n -= 1


T = int(input())
k = 1
while k <= T:
	n = int(input())
	A = list(map(int, input().split()))
	j = 0
	for i in range(n):
		if A[i] % 2 == 0:
			j += 1
	if j == n:
		print('0')
	else:
		print(j)
	k += 1


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


t = int(input())
for i in range(t):
	n = int(input())
	arrA = list(map(int, input().split()))
	count = 0
	n1 = len(arrA)
	for i in arrA:
		if i % 2 == 0:
			count = count + 1
	if count == 0 or count == n1:
		print(0)
	else:
		print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	eve = odd = 0
	for i in range(n):
		if a[i] % 2 == 0:
			eve += 1
		else:
			odd += 1
	if odd == n or eve == n:
		print(0)
	else:
		print(eve)


t = int(input())
for i in range(t):
	even = 0
	n = int(input())
	l = list(map(int, input().split()))
	for j in l:
		if j % 2 == 0 and j != 0:
			even += 1
	if even == len(l):
		print(0)
	else:
		print(even)


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	evenc = len(list(filter(lambda x: x % 2 == 0, a)))
	print(0 if evenc == 0 or n - evenc == 0 else evenc)


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


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(e, o) = (0, 0)
	for i in arr:
		e += int(i & 1 == 0)
		o += i & 1
	if not e or not o:
		print(0)
	else:
		print(e)


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