CF1693F.I Might Be Wrong

You are given a binary string $S$ of length $n$ indexed from $1$ to $n$. You can perform the following operation any number of times (possibly zero):

• Choose two integers $l$ and $r$ ($1 \le l \le r \le n$). Let $cnt_0$ be the number of times 0 occurs in $S[l \ldots r]$ and $cnt_1$ be the number of times 1 occurs in $S[l \ldots r]$. You can pay $|cnt_0 - cnt_1| + 1$ coins and sort the $S[l \ldots r]$. (by $S[l \ldots r]$ we mean the substring of $S$ starting at position $l$ and ending at position $r$)

  For example if $S = $ 11001, we can perform the operation on $S[2 \ldots 4]$, paying $|2 - 1| + 1 = 2$ coins, and obtain $S = $ 10011 as a new string.

Find the minimum total number of coins required to sort $S$ in increasing order.

给你一个长度为 $n$ 的二进制字符串 $S$，其下标从 $1$ 到 $n$。你可以执行以下操作任意次（可以为零次）：

• 选择两个整数 $l$ 和 $r$（满足 $1 \le l \le r \le n$）。令 $cnt_0$ 表示子串 $S[l \ldots r]$ 中字符 0 出现的次数，$cnt_1$ 表示子串 $S[l \ldots r]$ 中字符 1 出现的次数。你可以花费 $|cnt_0 - cnt_1| + 1$ 枚硬币，将子串 $S[l \ldots r]$ 升序排序。（这里 $S[l \ldots r]$ 表示字符串 $S$ 中从位置 $l$ 开始、到位置 $r$ 结束的子串）

  例如，若 $S = $ 11001，我们可以在子串 $S[2 \ldots 4]$ 上执行该操作，花费 $|2 - 1| + 1 = 2$ 枚硬币，得到新字符串 $S = $ 10011。

求将 $S$ 升序排序所需的最小总硬币数。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of $S$.

The second line of each test case contains a binary string $S$ of $n$ characters $S_1S_2 \ldots S_n$. ($S_i = $ 0 or $S_i = $ 1 for each $1 \le i \le n$)

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

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。随后是各测试用例的描述。

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

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $S$，记作 $S_1S_2 \ldots S_n$（对每个 $1 \le i \le n$，均有 $S_i = 0$ 或 $S_i = 1$）。

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

For each test case, output the minimum total number of coins required to sort $S$ in increasing order.

对于每个测试用例，输出将 $S$ 按升序排序所需的最少硬币总数。

In the first test case, $S$ is already sorted.

In the second test case, it's enough to apply the operation with $l = 1, r = 2$.

In the third test case, it's enough to apply the operation with $l = 1, r = 2$.

在第一个测试用例中，$S$ 已经是有序的。

在第二个测试用例中，只需对 $l = 1, r = 2$ 执行该操作。

在第三个测试用例中，只需对 $l = 1, r = 2$ 执行该操作。