Counting Even Sum Pairs

You are given one or more test cases. In each test case, you are provided with an array of n integers. Your task is to determine the number of unordered pairs of distinct elements \((x,y)\) such that the sum \(x+y\) is even.

The mathematical insight is that a sum of two integers is even if both integers are even or both are odd. In other words, if you have e even numbers and o odd numbers in the array, the total number of valid pairs is:

$$ \binom{o}{2} + \binom{e}{2} = \frac{o(o-1)}{2} + \frac{e(e-1)}{2} $$

You need to perform the above calculation for each test case.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains a single integer T representing the number of test cases.
2. For each test case, the first line contains an integer n — the number of elements in the array.
3. The next line contains n space-separated integers.

outputFormat

For each test case, output a single line containing the number of valid unordered pairs where the sum of the pair is even. The results are printed to stdout.

1
5
1 2 3 4 5

4