CF1693F I Might Be Wrong

给定一个长度为 $n$ 的 `01` 字符串 $S$。 你可以进行下列操作任意次： - 选择 $S$ 的一个连续子串 $S[l,r]$。 设 $cnt_0,cnt_1$ 分别表示该子段中字符 `0` 和字符 `1` 的数量。 则你将花费 $|cnt_0-cnt_1|+1$ 枚金币并对 $S[l,r]$ 进行升序排序。 你需要求出使 $S$ 本身升序排序所需的最少金币数。

第一行输入一个整数 $t(1\leq t\leq10^3)$ 表示数据组数，接下来对于每组数据： 第一行输入一个整数 $n(1\leq n,\sum n\leq2\times10^5)$。 接下来一行输入 $n$ 个字符表示 `01` 字符串 $S$。

对于每组数据： 输出对 $S$ 排序所需的最少金币数。 ### 样例解释 对于第三组数据： - 我们可以选择子串 $S[1,2]$，此时 $cnt_0=cnt_1=1$，因此花费 $|1-1|+1$，即 $1$ 枚金币。 操作后 $S=\texttt{"011"}$，满足要求，共计花费 $1$ 枚金币。 对于第六组数据： - 第一次操作选择子串 $S[1,4]$，此时 $cnt_0=cnt_1=2$，因此花费 $|2-2|+1$，即 $1$ 枚金币。 操作后 $S=\texttt{"001100"}$。 - 第二次操作选择子串 $S[3,6]$，此时 $cnt_0=cnt_1=2$，因此花费 $|2-2|+1$，即 $1$ 枚金币。 操作后 $S=\texttt{"000011"}$，满足要求，共计花费 $2$ 枚金币。

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