Even Sum Pairs

You are given an integer T representing the number of test cases. For each test case, you are provided an integer N and a list of N integers. Your task is to compute the number of pairs (i, j) (with i < j) such that the sum of the two numbers is even.

The sum of two integers is even if and only if both integers are even or both are odd. Formally, if the list contains e even numbers and o odd numbers, then the answer for that test case is \(\binom{e}{2} + \binom{o}{2}\), where \(\binom{n}{2} = \frac{n(n-1)}{2}\).

Implement a solution that reads from standard input and prints the result to standard output.

inputFormat

The first line contains an integer T, the number of test cases. Each test case consists of two lines:

• The first line contains an integer N, indicating the number of elements in the array.
• The second line contains N space-separated integers.

Input is provided via standard input (stdin).

outputFormat

For each test case, output the count of pairs (i, j) whose sum is even on a new line. Output is via standard output (stdout).

## sample

2
4
1 2 3 4
3
2 2 2

2
3

</p>