Using his tip-top physique, Kim has now climbed up the mountain where the base is located. Kim has found the door to the (supposedly) super secret base. Well, it is super secret, but obviously no match for Kim's talents. 
The door is guarded by a row of $N$ buttons. Every button has a single number $A_i$ written on it. Surprisingly, more than one button can have the same number on it. Kim recognises this as Soum's VerySafe door, for which you need to press two buttons to enter the password. More importantly, the sum of the two numbers on the buttons you press must be odd. Kim can obviously break through this door easily, but he also wants to know how many different pairs of buttons he can pick in order to break through the door.
Can you help Kim find the number of different pairs of buttons he can press to break through the door? 
Note: Two pairs are considered different if any of the buttons pressed in the pair is different (by position of the button pressed). Two pairs are not considered different if they're the same position of buttons, pressed in a different order. 
Please refer to the samples for more details.

-----Input:-----
- The first line contains a single integer $T$, representing the number of testcases. $2T$ lines follow, 2 for each testcase.
- For each testcase, the first line contains a single integer $N$, the number of buttons.
- The second line of each testcase contains $N$ space-separated integers, $A_1, A_2, \ldots, A_N$, representing the numbers written on each button.

-----Output:-----
Print a single number, $K$, representing the number of pairs of buttons in $A$ which have an odd sum.

-----Subtasks-----
For all subtasks,  $1 \leq T \leq 10$, $1 \leq N \leq 100000$, and $1 \leq A_i \leq 100000$ for all $A_i$.
Subtask 1 [15 points] : $N \leq 2$, There are at most 2 buttons
Subtask 2 [45 points] : $N \leq 1000$, There are at most 1000 buttons
Subtask 3 [40 points] : No additional constraints.

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

-----Sample Output:-----
3
0
0

-----EXPLANATION:-----
This section uses 1-indexing.
In the first sample, the buttons are: $[3, 5, 3, 4]$
$A[1] +  A[4] = 3 + 4 = 7$ which is odd.
$A[2] +  A[4] = 5 + 4 = 9$ which is odd.
$A[3] +  A[4] = 3 + 4 = 7$ which is odd.
In total, there are 3 pairs with an odd sum, so the answer is 3.
In the second sample, the buttons are: $[5, 7]$. There are no odd pairs, so the answer is $0$.
In the third sample, the buttons are: $[4]$. There are no pairs at all, so the answer is $0$.

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for i in range(n):
		if a[i] % 2 != 0:
			cnt = cnt + 1
	ans = n - cnt
	print(ans * cnt)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1 or (n == 2 and sum(l) % 2 == 0):
		print('0')
	else:
		l1 = [x for x in l if x % 2 == 0]
		l2 = [x for x in l if x % 2 != 0]
		print(len(l1) * len(l2))


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in a:
		if i % 2 != 0:
			count += 1
	c_even = len(a) - count
	print(count * c_even)


try:
	for _ in range(int(input())):
		n = int(input())
		li = list(map(int, input().split(' ')))
		lo = len(list(filter(lambda x: x % 2 == 1, li)))
		le = len(list(filter(lambda x: x % 2 == 0, li)))
		print(lo * le)
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	but = list(map(int, input().split()))
	odd = [i % 2 for i in but]
	no = odd.count(1)
	ne = odd.count(0)
	ans = no * ne
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	e = 0
	o = 0
	for i in l:
		if i % 2 == 0:
			e += 1
		if i % 2 != 0:
			o += 1
	print(e * o)


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


T = int(input())
for _ in range(T):
	n = int(input())
	buttons = list(map(int, input().split()))
	odds = 0
	evens = 0
	for button in buttons:
		if button % 2 == 0:
			evens += 1
		else:
			odds += 1
	print(int(odds * evens))


(t, i) = (int(input()), 1)
(even_count, odd_count) = (0, 0)
(evenset, oddset) = ([], [])
while i <= t:
	buttons_no = int(input())
	numbers = list(map(int, input().split()))
	for j in range(len(numbers)):
		if numbers[j] % 2 != 0:
			odd_count += 1
			oddset.append(j + 1)
		elif numbers[j] % 2 == 0:
			even_count += 1
			evenset.append(j + 1)
	print(odd_count * even_count)
	(even_count, odd_count) = (0, 0)
	(evenset, oddset) = ([], [])
	i += 1


n = int(input())
for i in range(n):
	a = int(input())
	lis = list(map(int, input().split()))
	o = 0
	for i in lis:
		if i % 2 != 0:
			o += 1
	print(o * (a - o))


t = int(input())
for i in range(t):
	n = int(input())
	x = map(int, input().split(' '))
	c = 0
	for i in x:
		if i % 2 == 0:
			c = c + 1
	s = n - c
	print(s * c)


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


t = int(input())
for i in range(0, t):
	n = int(input())
	listodd = []
	listeven = []
	a = input().split()
	for l in a:
		if int(l) % 2 == 0:
			listeven.append(int(l))
		else:
			listodd.append(int(l))
	print(len(listodd) * len(listeven))


t = int(input())
while t > 0:
	n = int(input())
	lst = list(map(int, input().split()))
	(ev, od) = (0, 0)
	for i in lst:
		if i % 2 == 0:
			ev += 1
		else:
			od += 1
	print(ev * od)
	t -= 1


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	even = 0
	odd = 0
	for j in range(0, len(A)):
		if A[j] % 2 == 0:
			even = even + 1
		if A[j] % 2 != 0:
			odd = odd + 1
	print(odd * even)


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


T = int(input())
for i in range(T):
	n = int(input())
	op = list(map(int, input().split()))
	count = 0
	for z in op:
		if z % 2 != 0:
			count += 1
	print(count * (n - count))


t = int(input())
for _ in range(t):
	num = int(input())
	l = list(map(int, input().split()))
	even = 0
	for i in l:
		if i % 2 == 0:
			even += 1
	odd = num - even
	print(odd * even)


from itertools import combinations

def check(a):
	c = 0
	if len(set(a)) == 1:
		return 0
	c_o = 0
	c_e = 0
	for i in a:
		if i % 2 == 0:
			c_e += 1
		else:
			c_o += 1
	return c_o * c_e
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(check(a))


passes = int(input())
while passes != 0:
	c = int(input())
	oc = 0
	ec = 0
	buttons = list(map(int, input().split()))
	n = 1
	for x in buttons:
		if x & 1 == 1:
			oc += 1
		else:
			ec += 1
	print(oc * ec)
	passes -= 1


for _ in range(int(input())):
	x = int(input())
	arr = list(map(int, input().split()))
	count = 0
	if x == 1:
		print('0')
	else:
		for i in arr:
			if i % 2 == 0:
				count += 1
		ak = x - count
		print(ak * count)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	c = Counter([int(x) % 2 for x in input().split()])
	print(c[0] * c[1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = []
	q = []
	for i in range(n):
		if a[i] % 2 == 0:
			p.append(a[i])
		else:
			q.append(a[i])
	r = len(p) * len(q)
	print(r)


t = int(input())
while t > 0:
	n = int(input())
	lst = list(map(int, input().split()))
	(count, count1) = (0, 0)
	for i in range(n):
		if lst[i] % 2 == 0:
			count += 1
		else:
			count1 += 1
	print(count * count1)
	t -= 1


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = [int(i) for i in input().split()]
	count = 0
	for i in range(n):
		if a[i] & 1 == 0:
			count += 1
	ans = n - count
	print(ans * count)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	e = []
	o = []
	for j in range(n):
		if l[j] % 2 == 0:
			e.append(l[j])
		if l[j] % 2 == 1:
			o.append(l[j])
	if e == [] or o == []:
		print(0)
	else:
		print(len(e) * len(o))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cnte = 0
	cnto = 0
	for i in l:
		if i % 2 == 0:
			cnte += 1
		else:
			cnto += 1
	res = cnte * cnto
	print(res)


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		(sum, c) = (0, 0)
		for i in range(len(l)):
			for j in range(i, len(l) - 1):
				sum = sum + l[j] + l[j + 1]
				if sum % 2 != 0:
					c = c + 1
		print(c)
except:
	pass


T = int(input())
for _ in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	(even, odd) = ([], [])
	for num in l:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	print(len(even) * len(odd))


for i in range(int(input())):
	x = int(input())
	lis = list(map(int, input().split(' ')))
	even = []
	odd = []
	for i in range(x):
		if lis[i] % 2 == 0:
			even.append(lis[i])
		if lis[i] % 2 == 1:
			odd.append(lis[i])
	if even == [] or odd == []:
		print(0)
	else:
		print(len(even) * len(odd))


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = 0
	d = 0
	for i in l:
		if i % 2 == 0:
			c += 1
		else:
			d += 1
	print(c * d)


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


ujju = int(input())
for jyi in range(ujju):
	arey = int(input())
	y = list(map(int, input().split()))
	w = []
	p = []
	for j in range(arey):
		if y[j] % 2 == 0:
			w.append(y[j])
		if y[j] % 2 == 1:
			p.append(y[j])
	if w == [] or p == []:
		print(0)
	else:
		print(len(w) * len(p))


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


T = int(input())
for x in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	if 1 <= T <= 10 and 1 <= N <= 100000 and (1 <= len(A) <= 100000):
		a = 0
		b = 0
		for x in range(N):
			if A[x] % 2 == 0:
				a += 1
			else:
				b += 1
		print(a * b)


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


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	even = []
	odd = []
	for i in a:
		if i & 1:
			even.append(i)
		else:
			odd.append(i)
	print(len(even) * len(odd))


import sys
import math

def main(arr):
	(odd, even) = (0, 0)
	ans = 0
	for e in arr:
		if e & 1:
			odd += 1
		else:
			even += 1
	for e in arr:
		if e & 1:
			ans += even
			odd -= 1
		else:
			ans += odd
			even -= 1
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(main(arr))


t = int(input())
for _ in range(t):
	input()
	t1 = [int(i) for i in input().strip().split(' ')]
	t1o = 0
	for i in t1:
		if i % 2 == 0:
			t1o += 1
	t1e = len(t1) - t1o
	print(t1e * t1o)


for I in range(int(input())):
	l = int(input())
	b = map(int, input().split())
	count = 0
	countodd = 0
	for j in b:
		if j % 2 == 0:
			count += 1
		else:
			countodd += 1
	print(count * countodd)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odds = 0
	for x in a:
		if x % 2 == 1:
			odds += 1
	evens = n - odds
	print(odds * evens)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	counto = 0
	counte = 0
	for i in l:
		if i % 2 == 0:
			counte += 1
		else:
			counto += 1
	print(counte * counto)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	s = 0
	for i in l:
		if i % 2 == 0:
			s += 1
	print((a - s) * s)


n = int(input())
for i in range(n):
	k = int(input())
	l = map(int, input().split())
	c = 0
	for j in l:
		if j % 2 == 0:
			c += 1
	s = k - c
	print(s * c)


for _ in range(int(input())):
	N = int(input())
	count = 0
	arr = list(map(int, input().split()))
	if len(arr) == 1:
		print('0')
	else:
		for i in range(len(arr)):
			if arr[i] % 2 == 0:
				for j in range(i + 1, len(arr)):
					if arr[j] % 2 != 0:
						count += 1
			elif arr[i] % 2 != 0:
				for j in range(i + 1, len(arr)):
					if arr[j] % 2 == 0:
						count += 1
		print(count)


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


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	d = 0
	for i in range(n):
		if l[i] % 2 == 0:
			c = c + 1
		elif l[i] % 2 != 0:
			d = d + 1
	print(c * d)


for _ in range(int(input())):
	n = int(input())
	oddcount = 0
	evencount = 0
	stri = input().split()
	for i in stri:
		if int(i) % 2:
			oddcount += 1
		else:
			evencount += 1
	print(oddcount * evencount)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	odds = 0
	for i in range(n):
		if a[i] % 2 == 1:
			odds = odds + 1
		evens = n - odds
	print(odds * evens)


t = int(input())
for ni in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	co = 0
	ce = 0
	for i in a:
		if i % 2 == 0:
			ce = ce + 1
		else:
			co = co + 1
	print(co * ce)


from math import factorial

def Combination(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r))
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(odd, even) = (0, 0)
	for i in l:
		if i & 1 == 1:
			odd += 1
		else:
			even += 1
	if even == 0 or odd == 0:
		print(0)
	else:
		print(Combination(odd, 1) * Combination(even, 1))


t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	o = e = 0
	for k in l:
		if k % 2 == 0:
			e += 1
		else:
			o += 1
	print(e * o)
	t -= 1


for i in range(int(input())):
	a = int(input())
	s = list(map(int, input().split()))
	l = []
	for i in s:
		if i % 2 != 0:
			l.append(i)
	print((a - len(l)) * len(l))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	odds = sum((a & 1 for a in A))
	evens = N - odds
	print(odds * evens)


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


for jj in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	eCount = len(list(filter(lambda x: x & 1 == 0, l)))
	oCount = len(list(filter(lambda x: x & 1 == 1, l)))
	print(eCount * oCount)


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().rstrip().split()]
	count = 0
	for i in a:
		if i % 2 == 0:
			count += 1
	s = n - count
	print(s * count)


from itertools import combinations
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	a = list(combinations(lst, 2))
	count = 0
	for i in range(len(a)):
		if sum(a[i]) % 2 != 0:
			count += 1
	print(count)


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = []
	for i in a:
		if i % 2 == 0:
			b.append(i)
		else:
			c.append(i)
	print(len(b) * len(c))


for j in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = []
	for i in range(n):
		if x[i] % 2 == 0:
			y.append(0)
		else:
			y.append(1)
	a = y.count(1)
	b = y.count(0)
	print(a * b)


def num_of_pairs(lst):
	(odd, even) = (0, 0)
	for num in lst:
		if num % 2 == 0:
			even += 1
		else:
			odd += 1
	return odd * even
t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	print(num_of_pairs(L))


for M in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	neg = 0
	pos = 0
	for i in l:
		if i % 2 == 0:
			pos += 1
		else:
			neg += 1
	print(pos * neg)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	odd_count = 0
	even_count = 0
	for j in range(len(a)):
		if a[j] % 2 == 1:
			odd_count += 1
		else:
			even_count += 1
	print(odd_count * even_count)


t = int(input())
for i in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	counteven = 0
	countodd = 0
	for ele in num:
		if ele % 2 == 0:
			counteven += 1
		else:
			countodd += 1
	print(countodd * counteven)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count1 = 0
	count2 = 0
	for i in range(n):
		if a[i] % 2 == 0:
			count1 += 1
		else:
			count2 += 1
	print(count1 * count2)


for i in range(int(input())):
	a = int(input())
	x = 0
	l = list(map(int, input().split()))
	for j in l:
		if j % 2 == 0:
			x += 1
	y = a - x
	print(y * x)


t = int(input())
for x in range(t):
	n = int(input())
	s = input().split()
	k = []
	for i in s:
		k.append(int(i))
	c1 = 0
	c2 = 0
	for i in k:
		if i % 2 == 0:
			c1 += 1
		else:
			c2 += 1
	print(int(c1 * c2))