Even Sum Pairs

You are given T test cases. In each test case, you are provided with an integer N and a sequence of N positive integers. Your task is to count the number of unique pairs (i, j) (with i < j) such that the sum of the i^th and j^th elements is even.

More formally, for an array \( A = [a_1, a_2, \ldots, a_N]\), count the pairs \((i, j)\) with \(1 \leq i < j \leq N\) such that: \[ a_i + a_j \equiv 0 \pmod{2} \]

Input is provided via standard input and output should be printed to standard output, with one result per test case on a new line.

inputFormat

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 number of elements in the sequence.
• The second line contains N space-separated positive integers.

outputFormat

For each test case, print a single number representing the count of unique pairs (i, j) such that i < j and \(a_i + a_j\) is even. Each result should be printed on a new line in the same order as the test cases.

## sample

1
4
1 2 3 4

2

</p>