Even Sum Subarrays

You are given an array arr consisting of n integers. Your task is to compute the number of contiguous subarrays whose sum is even.

A contiguous subarray is defined by a pair of indices i and j (with 1 ≤ i ≤ j ≤ n) corresponding to the subarray arr[i...j]. The sum of a subarray is even if it is divisible by 2, i.e. if sum mod 2 = 0.

A useful observation is that if you define prefix sums as \( p_k = a_1 + a_2 + \cdots + a_k \) (with \( p_0 = 0 \)), then the sum of the subarray arr[i...j] is even if and only if \( p_j - p_{i-1} \) is even. This is equivalent to \( p_j \) and \( p_{i-1} \) having the same parity.

Implement a solution that, for each test case, reads the array and outputs the count of contiguous subarrays with an even sum.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(T\) representing 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, output a single line to stdout containing the number of contiguous subarrays that have an even sum.

2
4
1 2 3 4
3
2 4 6

4
6