You are given an array A₁,A₂...A_N. You have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and A_i XOR A_j is odd.

Input and Output
First line T, the number of testcases. Each testcase: first line N, followed by N integers in next line. For each testcase, print the required answer in one line.

Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 10⁵
0 ≤ A_i ≤ 10⁹