Counting Even Sum Pairs

You are given an array of n integers a_1, a_2, \dots, a_n. Your task is to count the number of pairs \((i, j)\) such that \(1 \leq i < j \leq n\) and the sum \(a_i + a_j\) is even.

A sum \(a_i + a_j\) is even if both a_i and a_j are even or both are odd. In other words, if you let \(E\) be the number of even numbers and \(O\) the number of odd numbers in the array, then the number of valid pairs is given by:

[ \text{pairs} = \binom{E}{2} + \binom{O}{2} = \frac{E \times (E-1)}{2} + \frac{O \times (O-1)}{2} ]

You need to solve this problem for multiple test cases.

inputFormat

The first line of input contains a single integer T denoting the number of test cases.

For each test case:

• The first line contains a single integer n — the number of elements in the array.
• The second line contains n space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single line containing the number of pairs of indices \((i, j)\) such that \(a_i + a_j\) is even.

## sample

2
4
1 2 3 4
3
2 4 6

2
3

</p>