Count Even Sum Pairs

You are given a sequence of integers for each test case. Your task is to count the number of pairs (i, j) such that i ≤ j and the sum of the i^th and j^th number is even. Two numbers add up to an even number if and only if both numbers are even or both are odd. Formally, if we denote the number of even elements by \(E\) and the number of odd elements by \(O\), then the answer is given by:

[ \frac{E(E+1)}{2} + \frac{O(O+1)}{2} ]

Process each test case independently and output the result on a new line.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Then for each test case, the first line contains an integer \(N\), the number of elements, followed by a line with \(N\) space-separated integers.

Input is provided via standard input (stdin).

outputFormat

For each test case, output the count of pairs satisfying the condition on a new line to standard output (stdout).

## sample

2
4
1 2 3 4
3
1 1 1

6
6

</p>