Count Valid Pairs

You are given T test cases. For each test case, you are told the number of participants M and the list of their heights. Your task is to compute the number of valid pairs that can be formed according to the following rule:

A valid pair consists of one participant with an even height and one with an odd height. In other words, if a test case has E even numbers and O odd numbers, the number of valid pairs is

\(E \times O\)

Note: Each pair is unordered so pairing participant A (even height) with participant B (odd height) is the same as pairing participant B with participant A.

Input: The input is read from standard input (stdin).

Output: The output should be written to standard output (stdout), with each test case's result on a new line.

inputFormat

The first line contains an integer T, representing the number of test cases.

For each test case:

• The first line contains an integer M, the number of participants.
• The second line contains M space-separated integers representing the heights of the participants.

All input is given via standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the number of valid pairs, where a valid pair includes one even and one odd height.

Output the answers via standard output (stdout).

## sample

1
4
160 181 162 175

4

</p>