RoAlgo Contest #7 | muxusetre

"Life is hard. It's better to avoid all difficulties, just press the skip button!"

Mux was in the park and found $t$ strings of $0$s and $1$s on a bench. He needs to determine how many good subarrays each string contains. A subarray is considered good if the difference between the number of $0$s and $1$s in the subarray is even. Note that this difference does not necessarily have to be positive.

Task

Given $t$ strings, determine for each string how many subarrays have an even difference between the number of $0$s and $1$s.

Input data

The first line of the input contains the number $t$. For each $i \ (1 \leq i \leq t)$, the next two lines contain the length of the $i$-th string found by Mux and the string itself.

Output data

For each $i \ (1 \leq i \leq t)$, print the answer to Mux's question for the $i$-th string.

Constraints and clarifications

• $1 \leq t \leq 1\ 000$
• $1 \leq n \leq 10^6$, where $n$ is the length of each string
• The string contains only the characters $0$ and $1$.
• The sum of the lengths of all $t$ strings does not exceed $10^6$.
• Note. This problem has no relation to the problem suxumetre.

Example

stdin

4
9
010100100
7
0000000
18
100100010111010111
11
00000000000

stdout

20
12
81
30

Explanation

For the first string, some of the subarrays that meet the required property are 0101, 10, 1001, etc.