CF2188B Seats

Cordell 管理着 Piova 市立音乐学校的一排 $n$ 个座位，学校严格禁止学生彼此相邻就坐。 给定一个二进制字符串 $s$，其中 $s_i = \mathtt{1}$ 表示第 $i$ 个座位已经有学生就坐，而 $s_i = \mathtt{0}$ 表示当前空闲。保证当前不会有两个相邻的座位都已被占用。Cordell 需要继续安排更多学生，直到无法再安排任何学生，但她希望用尽可能少的新学生就达到这种“无法再安排”状态。 你的任务是计算，当无法再安排任何新学生时，排中最少的总就座学生人数。 $^\text{∗}$ 二进制字符串指每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

每个测试点包含多组测试数据。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。每组测试数据描述如下。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示这一排有 $n$ 个座位。 第二行包含一个长度为 $n$ 的二进制字符串 $s$（$s_i \in \{\mathtt{0}, \mathtt{1}\}$）。保证字符串中不会有两个相邻的 $\mathtt{1}$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示达到无法再就座时，排中最少的总就坐学生人数。

在第一个测试用例中，$n=1$，初始时教室是空的。由于还可以安排学生，Cordell 必须安排一名学生坐在第 1 号座位。此时就座人数最少为 $1$。 在第三个测试用例中，Cordell 可以安排两名学生分别坐在第 1 和第 4 个座位。可以证明，无论如何安排一名学生，都无法让排无法继续安排新生，因此答案为 $2$。 在第四个测试用例中，无法再安排新学生，所以 Cordell 不需要额外安排，他总共安排的学生人数是 $3$。 由 ChatGPT 5 翻译