Given an array $A$ of size $N$ , count number of pairs of index $i,j$ such that $A_i$ is even, $A_j$ is odd and $i < j$

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases.   
- The first line of each test case contains integer $N$.    
- The second line of each test case contains $N$ space separated integers $A_i$. 

-----Output-----
For each test case, print a single line containing an integer denoting number of pairs.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N \le 10^5$ 
- $1 \le A_i \le 10^9$
- Sum of $N$ over all test cases doesn't exceed $10^6 $ 

-----Subtasks-----
Subtask #1 (30 points):
- $2 \le N \le 100$ 
Subtask #2 (70 points): original constraints

-----Example Input-----
2
4
1 2 1 3
5
5 4 1 2 3

-----Example Output-----
2
3

-----Explanation-----
Example case 1:$(A_2,A_3)$ and $(A_2,A_4)$ . 
Example case 2:$(A_2,A_3)$ , $(A_2,A_5)$ and $(A_4,A_5)$  .

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	counter = 0
	even = 0
	for num in l:
		if num % 2 == 0:
			even += 1
		if num % 2 == 1:
			counter += even
	print(counter)


for t in range(int(input())):
	n = int(input())
	numberlist = list(map(int, input().split()))
	count = 0
	for i in range(len(numberlist) - 1):
		for j in range(i + 1, len(numberlist)):
			if numberlist[i] % 2 == 0:
				if numberlist[j] % 2 == 1:
					count += 1
	print(count)


x = int(input())
for k in range(x):
	y = int(input())
	a = list(map(int, input().split()))[:y]
	m = 0
	for i in range(y):
		for j in range(i + 1, y):
			if a[i] % 2 == 0 and a[j] % 2 != 0:
				m += 1
			else:
				continue
	print(m)


x = int(input())
for _ in range(x):
	a = int(input())
	l = list(map(int, input().split()))
	(od, ev, re) = (0, 0, 0)
	for i in range(a):
		if l[i] % 2 == 0:
			ev += 1
		else:
			od += 1
			re += ev
	print(re)


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


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


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


t = int(input())
for x in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	i = 0
	count = 0
	while i < n:
		if a[i] % 2 == 0:
			j = i + 1
			p = 0
			while j < n:
				if a[j] % 2 != 0:
					p += 1
				j += 1
			count += p
		i += 1
	print(count)


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


t = int(input())
for i in range(t):
	n = int(input())
	ans = 0
	a = list(map(int, input().split()))
	for j in range(n - 1):
		for k in range(j + 1, n):
			if j < k and a[j] % 2 == 0 and (a[k] % 2 != 0):
				ans += 1
	print(ans)


from itertools import product
t = int(input())
for i in range(t):
	n = int(input())
	ans = 0
	a = list(map(int, input().split()))
	for (j, k) in product(list(range(len(a) - 1)), list(range(1, len(a)))):
		if j < k and a[j] % 2 == 0 and (a[k] % 2 != 0):
			ans += 1
	print(ans)


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


def pairs(arr):
	x = 0
	pairs = 0
	for i in range(len(arr)):
		if arr[i] % 2 == 0:
			x = x + 1
		else:
			pairs = pairs + x
	return pairs
test_cases = int(input())
for i in range(test_cases):
	x = int(input())
	arr = list(map(int, input().rstrip().split()))
	print(pairs(arr))