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: interview

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)

# cook your dish here
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)

# cook your dish here
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)

# cook your dish here
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)

# cook your dish here
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)


# cook your dish here
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)

# cook your dish here
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[i]%2==0 and 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
 j = 0
 while (j<n):
  if a[j]%2==0:
   i += 1
  else:
   count += i
  j += 1
 print(count)


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)


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) 

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


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) 


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


# cook your dish here
t=int(input())
for i in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 c=0
 odd=0
 for k in range(n-2,-1,-1):
  if a[k+1]%2!=0:
   odd+=1
  if a[k]%2==0:
   c+=odd
 print(c)
  


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


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


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) 

# cook your dish here
for _ in range(int(input())):
 n = int(input())
 l = list(map(int,input().split()))
 count = 0
 for i in range(n-1):
  if l[i]%2==0:
   for j in range(i+1,n):
    if l[j]%2!=0:
     count+=1
 print(count) 

# cook your dish here
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))

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