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 翻译