Count Odd Sum Subarrays

Given an integer array A of length N, your task is to count the number of contiguous subarrays that have an odd sum. A subarray is defined as a contiguous sequence of elements from the array. More formally, for a subarray starting at index l and ending at index r (1-indexed), its sum is \( S = \sum_{i=l}^{r} A_i \). This subarray has an odd sum if and only if \( S \mod 2 \equiv 1 \).

A useful observation is that if we consider the prefix sums \( P \) (where \( P_0 = 0 \) and \( P_i = A_1 + A_2 + \dots + A_i \) for \( i \geq 1 \)), then the sum of the subarray [l+1, r] is \( P_r - P_l \). Notice that the difference \( P_r - P_l \) is odd if and only if \( P_r \) and \( P_l \) have opposite parities. Based on this principle, you can count the number of subarrays with an odd sum by maintaining counts of even and odd prefix sums as you iterate through the array.

inputFormat

The input begins with an integer T (\(1 \leq T \leq 10^5\)) representing the number of test cases. Each test case is described over two lines:

• The first line contains a single integer N (\(1 \leq N \leq 10^5\)), the number of elements in the array.
• The second line contains N space-separated integers, representing the elements of the array.

It is guaranteed that the sum of N over all test cases does not exceed \(10^6\).

outputFormat

For each test case, output a single integer on a new line — the number of subarrays whose sum is odd.

## sample

1
3
1 2 3

4

</p>