CF2188B.Seats

Cordell manages a row of $n$ seats at the Scuola Comunale di Musica Piova where students are strictly forbidden from sitting next to each other.

You are given a binary string$^{\text{∗}}$ $s$, where $s_i = \mathtt{1}$ indicates that the $i$-th seat has been occupied by a student, and $s_i = \mathtt{0}$ indicates that it is free now. It is guaranteed that no two adjacent seats are occupied currently. Cordell needs to add more students until it is impossible to seat anyone else in the row. However, she wants to achieve this state with as few students as possible.

Your task is to calculate the minimum total number of students seated when it is impossible to seat anyone else in the row.

$^{\text{∗}}$A binary string is a string where each character is either $\mathtt{0}$ or $\mathtt{1}$.

科尔德尔负责管理皮奥瓦社区音乐学校（Scuola Comunale di Musica Piova）一排共 $n$ 个座位，学生被严格禁止相邻而坐。

你将得到一个二进制字符串$^{\text{∗}}$ $s$，其中 $s_i = \mathtt{1}$ 表示第 $i$ 个座位已被一名学生占据，而 $s_i = \mathtt{0}$ 表示该座位当前空闲。题目保证：当前不存在两个相邻的被占据座位。科尔德尔需要继续添加学生，直到整排座位再也无法容纳任何新学生为止。然而，她希望以最少的学生总数达成这一最终状态。

你的任务是：计算当整排座位再也无法容纳任何新学生时，所坐学生的最小总数。

$^{\text{∗}}$所谓二进制字符串，是指其中每个字符均为 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of seats in the row.

The second line of each test case contains the binary string $s$ of length $n$ ($s_i \in {\mathtt{0}, \mathtt{1}}$). It is guaranteed that no two adjacent characters are both $\mathtt{1}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示该排座位的数量。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$（$s_i \in {\mathtt{0}, \mathtt{1}}$）。保证不存在两个相邻字符均为 $\mathtt{1}$。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the minimum total number of seated students.

对于每个测试用例，输出一个整数——即就座学生的最少总人数。

In the first test case, $n = 1$ and the hall is initially empty. Because the row is still possible to seat any student, Cordell must place one student at seat $1$. Therefore, the minimum number of seated students is $1$.

In the third test case, Cordell can place two students at seats $1$ and $4$. It can be shown that she cannot place only one student so that the row is impossible to seat anyone more, so the answer is $2$.

In the fourth test case, no extra students can be seated, so Cordell can place no extra students, and the number of seated students is $3$.

在第一个测试用例中，$n = 1$，且礼堂初始为空。由于该排仍有可能安排任何学生就座，科德尔必须在座位 $1$ 安排一名学生。因此，就座学生的最小数量为 $1$。

在第三个测试用例中，科德尔可以在座位 $1$ 和 $4$ 各安排一名学生。可以证明，她无法仅安排一名学生便使得该排再也无法安排任何额外的学生，因此答案为 $2$。

在第四个测试用例中，无法再安排任何额外的学生，因此科德尔不能安排任何额外的学生，就座学生的数量为 $3$。