Vanishing String

You are given a string $S$ consisting only of 0 and 1.

You may perform the following operation any number of times.

Choose two equal adjacent characters and delete both of them simultaneously. After the deletion, the remaining parts are joined together.

A string is called a vanishing string if it can become the empty string using only this operation.

For every integer pair $(l,r)$ with $1 \leq l \leq r \leq N$, consider the substring $S_lS_{l+1}\cdots S_r$. Count how many of these substrings are vanishing strings.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $S$

For each test case, print the number of vanishing substrings on one line.

• $1 \leq T \leq 100$.
• $1 \leq N \leq 200\,000$.
• The length of $S$ is $N$.
• $S$ consists only of 0 and 1.
• The sum of $N$ over all test cases does not exceed $200\,000$.