muxusetre

Time limit: 0.1s Memory limit: 1MB Input: Output:

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

Mux was in the park and found tt strings of 00s and 11s 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 00s and 11s in the subarray is even. Note that this difference does not necessarily have to be positive.

Task

Given tt strings, determine for each string how many subarrays have an even difference between the number of 00s and 11s.

Input data

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

Output data

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

Constraints and clarifications

  • 1t1 0001 \leq t \leq 1\ 000
  • 1n1061 \leq n \leq 10^6, where nn is the length of each string
  • The string contains only the characters 00 and 11.
  • The sum of the lengths of all tt strings does not exceed 10610^6.
  • Note. This problem has no relation to the problem suxumetre.
# Points Constraints
1 0 Example
2 23 1n1001 \leq n \leq 100
3 36 1n1 0001 \leq n \leq 1\ 000
4 13 The string contains only 00s
5 23 No additional constraints

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.

Log in or sign up to be able to send submissions!