Count Good Pairs

Given an array of integers, a pair \( (i, j) \) with \( i < j \) is called a good pair if the sum of the two numbers is even, i.e., \(nums[i] + nums[j]\) is even.

A key observation is that the sum of two integers is even if both are even or both are odd. Hence, if there are even even numbers and odd odd numbers, the total number of good pairs is given by:

\(\binom{even}{2} + \binom{odd}{2} = \frac{even \times (even-1)}{2} + \frac{odd \times (odd-1)}{2}\)

Your task is to compute the number of good pairs for each test case.

inputFormat

The first line contains an integer (T), denoting the number of test cases. For each test case, the first line contains an integer (n), the size of the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

For each test case, print a single line containing the number of good pairs.## sample

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

4
6
1