Count Even Sum Pairs

You are given an array of integers. Your task is to count the number of unordered pairs (i, j) such that the sum of the elements at these indices is even. Two pairs (i, j) and (j, i) are considered the same, and i must not be equal to j.

The approach is to count the number of even and odd integers in the array. Two even numbers add up to an even number, and two odd numbers add up to an even number. The total number of valid unordered pairs will be the sum of the combinations taken 2 from the count of even numbers and the count of odd numbers.

inputFormat

The first line contains an integer T, representing the number of test cases. Each test case consists of two lines. The first line of each test case contains an integer n, the number of elements in the array. The second line contains n space-separated integers representing the array.

outputFormat

For each test case, output a single integer on a new line representing the number of unordered pairs (i, j) such that the sum of the two elements is even.## sample

2
4
1 2 3 4
3
5 7 9

2
3