hitman-and-xor

Hitman have an array x1,x2...xN of n elements. You have to tell how many pairs (a,b) 
exist such that 1 ≤ a < b ≤ N and x[a] XOR x[b] is odd.

Input
First line T, the number of testcases. Each testcase: first line N, followed by N 
integers in next line. 

Output 
For each testcase, print the required answer in one line.

Constraints 
1 ≤ T ≤ 10  
1 ≤ N ≤ 10^5  
0 ≤ A[i] ≤ 10^9    

SAMPLE INPUT
2
3
2 3 4
4
2 3 4 5

SAMPLE OUTPUT
2
4

Explanation

For first testcase:  2 XOR 3 is 1 and 3 XOR 4 is 7. So, 2 valid pairs .
For second testcase: 2 XOR 3 is 1 and 3 XOR 4 is 7 and 2 XOR 5 is 7 and 4 XOR 5 is 1. 
So, 4 valid pairs.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: