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
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.