Counting Subarrays with Even Sum

Given an array of integers, your task is to count the number of contiguous subarrays (subsegments) whose sum is even. A subarray is defined by a pair of indices (i, j) such that 0 ≤ i ≤ j < N, and its sum is the sum of elements from index i to j.

A useful observation is that if the cumulative (prefix) sums at two indices have the same parity (both even or both odd), the subarray between these indices has an even sum. Mathematically, if (P[i]) and (P[j+1]) have the same parity then (P[j+1]-P[i]) is even.

This problem tests your ability to implement an efficient algorithm with a linear time solution. Ensure your solution reads input from standard input (stdin) and writes output to standard output (stdout).

inputFormat

The first line contains an integer (T) ((1 \le T \le 100)) denoting the number of test cases. For each test case, the first line contains an integer (N) ((1 \le N \le 10^5)) representing the number of elements in the array. The second line contains (N) space-separated integers representing the array elements.

outputFormat

For each test case, output a single line containing the number of subarrays with an even sum.## sample

2
3
1 2 3
4
1 2 3 4

2
4