Count Even Sum Pairs

You are given T queries. In each query, an array of integers is provided. Your task is to count the number of distinct pairs \( (i,j) \) (with \( i < j \)) such that the sum of the two numbers is even.

Recall that the sum of two integers is even if and only if both are even or both are odd. In other words, if a query contains \( e \) even numbers and \( o \) odd numbers, then the number of valid pairs is:

\[ \frac{e(e-1)}{2} + \frac{o(o-1)}{2} \]

Compute and output this value for each query.

inputFormat

The input begins with an integer \( T \) representing the number of queries. For each query:

• The first line contains an integer \( n \), the number of elements in the array.
• The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \).

All the queries are given sequentially.

outputFormat

For each query, output a single line containing an integer which is the count of valid pairs whose sum is even.

## sample

2
4
1 2 3 4
6
2 4 6 8 10 12

2
15

</p>