Count Odd Sum Pairs

You are given an integer T, representing the number of test cases. For each test case, you are provided with an integer N and a sequence of N integers.

Your task is to count the number of distinct pairs \( (i, j) \) with \( i < j \) such that the sum of the \( i\)-th and \( j\)-th numbers is odd. A sum is odd if one of the numbers is odd and the other is even. The answer for each test case is the product of the count of odd numbers and the count of even numbers in the sequence.

Example:

Input:
1
3
1 2 3
Output:
2

In the above example, there are 2 odd numbers (1 and 3) and 1 even number (2), so the number of valid pairs is \(2 \times 1 = 2\).

inputFormat

The input is read from standard input (stdin). The first line contains an integer T denoting the number of test cases. Each test case consists of two lines: the first line contains an integer N (the size of the array), and the second line contains N space-separated integers.

outputFormat

For each test case, output a single line containing the number of pairs ( (i, j) ) (with ( i < j )) for which the sum of the corresponding elements is odd. The output should be written to standard output (stdout).## sample

1
3
1 2 3

2