CF1430D String Deletion

你有一个长度为 $n$ 的字符串 $s$，每个字符都是 $0$ 或 $1$。 你可以对字符串进行如下操作。每次操作包含两个步骤： 1. 选择一个整数 $i$，$1 \leq i \leq$ 字符串 $s$ 的长度，然后删除字符 $s_i$（字符串长度减少 $1$，被删除字符右侧的字符下标也相应减少 $1$）； 2. 如果字符串 $s$ 还不为空，删除最大长度的前缀，且该前缀所有字符都相同（剩余字符的下标和字符串长度也相应减少被删除前缀的长度）。 注意，每次操作的两个步骤都是必须的，且顺序不能更改。 例如，若有字符串 $s = 111010$，第一次操作可以有以下几种选择： 1. 选择 $i = 1$：得到 $111010 \rightarrow 11010 \rightarrow 010$； 2. 选择 $i = 2$：得到 $111010 \rightarrow 11010 \rightarrow 010$； 3. 选择 $i = 3$：得到 $111010 \rightarrow 11010 \rightarrow 010$； 4. 选择 $i = 4$：得到 $111010 \rightarrow 11110 \rightarrow 0$； 5. 选择 $i = 5$：得到 $111010 \rightarrow 11100 \rightarrow 00$； 6. 选择 $i = 6$：得到 $111010 \rightarrow 11101 \rightarrow 01$。 当字符串 $s$ 变为空时，操作结束。你能执行的最大操作次数是多少？

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示字符串 $s$ 的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，每个字符都是 $0$ 或 $1$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示你能执行的最大操作次数。

在第一个测试用例中，你可以例如选择 $i = 2$，第一次操作后得到字符串 010。之后可以选择 $i = 3$，得到字符串 1。最后只能选择 $i = 1$，得到空字符串。 由 ChatGPT 4.1 翻译