Count Even Sum Pairs

You are given an array of integers. Your task is to determine the number of pairs (i, j) with i < j such that the sum of the elements a[i] + a[j] is even.

A pair of integers will have an even sum if both integers are even or both are odd. Mathematically, if there are n even numbers in the array, the number of ways to choose 2 out of them is given by the formula \( \binom{n}{2} = \frac{n(n-1)}{2} \). Similarly, if there are m odd numbers, then the number of ways to choose 2 out of them is \( \binom{m}{2} = \frac{m(m-1)}{2} \).

Your goal is to compute the sum of these two quantities for the given array.

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 starts with an integer N (the size of the array), followed by N space-separated integers representing the array elements.

outputFormat

For each test case, output a single integer representing the number of pairs whose sum is even. Each answer should be printed on a new line to standard output (stdout).## sample

3
3
1 2 3
4
1 2 3 4
5
2 2 2 2 2

1
2
10