CF2237D.Fullmetal Bitchemist

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.

二进制字符串是指仅由字符 $0$ 和 $1$ 组成的字符串。字符 $0$ 和 $1$ 被称为互异值（opposite values）。

考虑一个二进制字符串 $t$。记 $|t|$ 为 $t$ 的长度。当 $|t| \ge 2$ 时，对每个满足 $1 \le i \lt |t|$ 的下标 $i$，字符 $t_i$ 和 $t_{i+1}$ 称为相邻。

若一个二进制字符串 $t$ 可通过任意多次（包括零次）执行如下操作而化简为长度恰好为 $1$ 的字符串，则称其为优美的（beautiful）：

• 选择一对相等的相邻字符，移除这两个字符，并在它们原来的位置插入一个与其值互异的字符。

例如，字符串 $\mathtt{10001}$ 可通过将首对相邻字符 $\mathtt{00}$ 替换为 $\mathtt{1}$，变为 $\mathtt{1101}$；接着可变为 $\mathtt{001}$，再变为 $\mathtt{11}$，最终变为 $\mathtt{0}$。因此，$\mathtt{10001}$ 是优美的。

另一方面，$\mathtt{111}$ 并不优美：执行一次操作后变为 $\mathtt{01}$，此后无法再执行任何操作。

现给定一个二进制字符串 $s$，请计算 $s$ 中非空优美子串$^{\text{∗}}$ 的个数。

$^{\text{∗}}$ 字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可通过从 $b$ 的开头删除若干（可能为零或全部）字符、并从 $b$ 的末尾删除若干（可能为零或全部）字符而得到。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

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

对于每个测试用例，输出一个整数——字符串 $s$ 的优美子串的数量。

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.

在第一个测试用例中，唯一的非空子串是 $\mathtt{0}$，它本身就是一个长度为 $1$ 的二进制字符串，因此它是优美的。

在第二个测试用例中，优美的子串是 $\mathtt{0}$ 和 $\mathtt{1}$。子串 $\mathtt{01}$ 不优美，因为它的两个字符不相等，因此无法执行任何操作。

在第三个测试用例中，优美的子串有：

• $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}$，它可以变为 $\mathtt{1}$；
• $s[2,4]=\mathtt{100}$，它可以变为 $\mathtt{11}$，再变为 $\mathtt{0}$；
• $s[3,5]=\mathtt{001}$，它可以变为 $\mathtt{11}$，再变为 $\mathtt{0}$；
• $s[1,4]=\mathtt{0100}$，它可以变为 $\mathtt{011}$，再变为 $\mathtt{00}$，最后变为 $\mathtt{1}$；
• $s[1,5]=\mathtt{01001}$，它可以变为 $\mathtt{0111}$，再变为 $\mathtt{001}$，然后变为 $\mathtt{11}$，最终变为 $\mathtt{0}$。

因此，共有 $10$ 个优美的子串。