Elegant Pairs

You are given several test cases. In each test case, you are provided with an array of integers of size n. Your task is to count the number of elegant pairs in the array. A pair of integers is considered elegant if both numbers are even or both are odd.

For a given test case, let the number of even integers be E and the number of odd integers be O. The number of elegant pairs can be calculated by the combination formula:

\(\binom{E}{2} + \binom{O}{2} = \frac{E(E-1)}{2} + \frac{O(O-1)}{2}\)

Compute and output the count of elegant pairs for each test case.

inputFormat

The input begins with an integer T, the number of test cases. Each test case consists of two lines. The first line contains a single integer n indicating the size of the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single integer on a new line indicating the number of elegant pairs.## sample

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

4
2