CF1750H.BinaryStringForces

You are given a binary string $s$ of length $n$. We define a maximal substring as a substring that cannot be extended while keeping all elements equal. For example, in the string $11000111$ there are three maximal substrings: $11$, $000$ and $111$.

In one operation, you can select two maximal adjacent substrings. Since they are maximal and adjacent, it's easy to see their elements must have different values. Let $a$ be the length of the sequence of ones and $b$ be the length of the sequence of zeros. Then do the following:

• If $a \ge b$, then replace $b$ selected zeros with $b$ ones.
• If $a \lt b$, then replace $a$ selected ones with $a$ zeros.

As an example, for $1110000$ we make it $0000000$, for $0011$ we make it $1111$. We call a string being good if it can be turned into $1111...1111$ using the aforementioned operation any number of times (possibly, zero). Find the number of good substrings among all $\frac{n(n+1)}{2}$ non-empty substrings of $s$.

给你一个长度为 $n$ 的二进制字符串 $s$。我们定义极大子串为：无法在保持所有字符相等的前提下进一步向左右扩展的子串。例如，在字符串 $11000111$ 中，存在三个极大子串：$11$、$000$ 和 $111$。

一次操作中，你可以选择两个相邻的极大子串。由于它们是极大且相邻的，显然它们所含字符必定不同。设 $a$ 为其中全 $1$ 子串的长度，$b$ 为其中全 $0$ 子串的长度。然后执行以下操作：

• 若 $a \ge b$，则将选中的 $b$ 个 $0$ 全部替换为 $b$ 个 $1$；
• 若 $a \lt b$，则将选中的 $a$ 个 $1$ 全部替换为 $a$ 个 $0$。

例如，对 $1110000$ 执行该操作后得到 $0000000$；对 $0011$ 执行该操作后得到 $1111$。若一个字符串可通过上述操作（可执行任意多次，包括零次）变为全 $1$ 字符串 $1111\ldots1111$，则称其为好字符串。求 $s$ 的所有 $\frac{n(n+1)}{2}$ 个非空子串中，好字符串的个数。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

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

It is guaranteed that sum of $n$ across all test cases doesn't exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。

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

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print a single integer — the number of good substrings.

对于每个测试用例，输出一个整数——即“好”子串的数量。

Let's define a substring from index $l$ to index $r$ as $[l, r]$.

For the first test case, the good substrings are:

• $[1,1]$,
• $[1,2]$,
• $[3,6]$,
• $[4,5]$,
• $[4,6]$,
• $[5,5]$,
• $[5,6]$,
• $[6,6]$.

In the second test case, all substrings are good except $[2,2]$.

In the third test case, all substrings are good.

我们定义从索引 $l$ 到索引 $r$ 的子串为 $[l, r]$。

对于第一个测试用例，所有“好”的子串为：

• $[1,1]$，
• $[1,2]$，
• $[3,6]$，
• $[4,5]$，
• $[4,6]$，
• $[5,5]$，
• $[5,6]$，
• $[6,6]$。

在第二个测试用例中，除 $[2,2]$ 外，所有子串都是“好”的。

在第三个测试用例中，所有子串都是“好”的。