AT_tupc2024_e 010-11 Shorten

给定一个长度为 $N$ 的只包含 `0` 和 `1` 的字符串 $S$。 你可以反复对字符串 $S$ 进行以下两种操作： - 操作 1：选择 $S$ 中的某个连续子串 `010`，并将其替换为 `1`。 - 操作 2：选择 $S$ 中的某个连续子串 `11`，并将其替换为 `1`。 请你求出最多可以进行多少次这样的操作。 给定 $T$ 组测试用例，请分别求解每组的答案。

输入以如下格式通过标准输入给出： > $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ 每组测试用例格式如下： > $N$ $S$

请输出 $T$ 行。对于 $i=1,2,\dots,T$，第 $i$ 行输出第 $i$ 个测试用例的答案（一个整数）。

### 样例解释 1 对于第 $1$ 个测试用例，例如可以进行如下 $3$ 次操作： - 对 `010100` 的第 $3$ 到 $5$ 个字符 `010` 进行操作 1，变为 `0110`。 - 对 `0110` 的第 $2$ 到 $3$ 个字符 `11` 进行操作 2，变为 `010`。 - 对 `010` 的第 $1$ 到 $3$ 个字符 `010` 进行操作 1，变为 `1`。 对于 `010100`，无法再进行超过 $3$ 次操作，因此答案为 $3$。 ### 数据范围 - $1 \leq T \leq 10^5$ - $1 \leq N \leq 10^6$ - $S$ 是长度为 $N$ 的只包含 `0` 和 `1` 的字符串 - 所有测试用例中 $N$ 的总和不超过 $10^6$ - $T, N$ 均为整数 由 ChatGPT 5 翻译