Subarrays with Equal Number of Even and Odd Integers

You are given an array of integers. A subarray is defined as a contiguous part of the array. Your task is to count the number of subarrays in which the number of even integers equals the number of odd integers.

Formally, for an array A of length n, consider a subarray A[i...j] (with 0 ≤ i ≤ j < n). Let \(count_{even}\) be the number of even numbers and \(count_{odd}\) the number of odd numbers in that subarray. The subarray is valid if and only if \(count_{even} = count_{odd}\).

Consider multiple test cases where you have to output the count for each test case on a new line.

inputFormat

The input begins with a single integer \(T\) representing the number of test cases. Each test case consists of two lines:

• The first line 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 line containing one integer — the count of subarrays where the number of even integers equals the number of odd integers.

## sample

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

9
4
0
0
4

</p>