D. Fullmetal Bitchemist

Source: Codeforces 2237D
Contest: Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
Time limit: 2 seconds
Memory limit: 256 megabytes

Statement

A binary string is a string consisting only of characters $0$ and $1$. The two characters $0$ and $1$ are called opposite values.

Consider a binary string $t$. Let $|t|$ be the length of $t$. When $|t| \ge 2$, for every $1 \le i \lt |t|$, the characters $t_i$ and $t_{i+1}$ are adjacent.

A binary string $t$ is called beautiful if it can be reduced to a string of length exactly $1$ by applying the following operation any number of times, possibly zero:

• Choose two equal adjacent characters, remove both of them, and insert one character with the opposite value in their place.

For example, the string $\mathtt{10001}$ can become $\mathtt{1101}$ by replacing the first adjacent pair $\mathtt{00}$ with $\mathtt{1}$. Then it can become $\mathtt{001}$, then $\mathtt{11}$, and finally $\mathtt{0}$. Therefore, $\mathtt{10001}$ is beautiful.

On the other hand, $\mathtt{111}$ is not beautiful. After one operation, it becomes $\mathtt{01}$, and then no operation can be applied.

You are given a binary string $s$. Compute the number of non-empty beautiful substrings$^{\text{∗}}$ of $s$.

$^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^6$) — the length of $s$.

The second line of each test case contains a binary string $s$ of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer — the number of beautiful substrings of $s$.

Note

In the first test case, the only non-empty substring is $\mathtt{0}$, which is already a binary string of length $1$. Therefore, it is beautiful.

In the second test case, the beautiful substrings are $\mathtt{0}$ and $\mathtt{1}$. The substring $\mathtt{01}$ is not beautiful, because its two characters are not equal, so no operation can be applied.

In the third test case, the beautiful substrings are:

• $s[1,1]=\mathtt{0}$;
• $s[2,2]=\mathtt{1}$;
• $s[3,3]=\mathtt{0}$;
• $s[4,4]=\mathtt{0}$;
• $s[5,5]=\mathtt{1}$;
• $s[3,4]=\mathtt{00}$, which can become $\mathtt{1}$;
• $s[2,4]=\mathtt{100}$, which can become $\mathtt{11}$, then $\mathtt{0}$;
• $s[3,5]=\mathtt{001}$, which can become $\mathtt{11}$, then $\mathtt{0}$;
• $s[1,4]=\mathtt{0100}$, which can become $\mathtt{011}$, then $\mathtt{00}$, then $\mathtt{1}$;
• $s[1,5]=\mathtt{01001}$, which can become $\mathtt{0111}$, then $\mathtt{001}$, then $\mathtt{11}$, and finally $\mathtt{0}$.

Thus, there are $10$ beautiful substrings.

Examples

10
1
0
2
01
5
01001
3
001
6
011110
9
010110110
12
010000101001
16
1010011010010110
20
11110101101101001110
30
000101100011111001111100000010

1
2
10
5
15
30
47
81
139
316