Hitman and XOR

0

0 votes
Problem

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

Time Limit: 2
Memory Limit: 256
Source Limit:
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.

Editor Image

?