"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.

# | Points | Constraints |
---|---|---|

1 | 0 | Example |

2 | 23 | $1 \leq n \leq 100$ |

3 | 36 | $1 \leq n \leq 1\ 000$ |

4 | 13 | The string contains only $0$s |

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.