← 返回题目列表

Codeforces · 2188/B

B. 座位

中文机器翻译题面 查看原题

Cordell 管理着一排 $$$n$$$ 座位 Scuola Comunale di Musica Piova 严禁学生坐在一起。

给你一个二进制字符串$$$^{\text{*}}$$$ $$$s$$$,其中$$$s_i = \mathtt{1}$$$ 表示第 $$$i$$$ 座位已被学生占用,$$$s_i = \mathtt{0}$$$ 表示该座位现在空闲。保证当前没有两个相邻座位被占用。科德尔需要增加更多的学生,直到排中无法容纳其他人为止。不过,她想用尽可能少的学生来达到这种状态。

你的任务是计算最小值 总计 当排中无法容纳其他人时就座的学生人数。

$$$^{\text{*}}$$$二进制字符串是每个字符为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$ 的字符串。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,输出一个整数 - 就座学生的最小总数。

示例

输入
复制

5
1
0
3
000
5
00000
6
100101
13
0000100001000

输出
复制

1
1
2
3
5

注意

在第一个测试用例中,$$$n = 1$$$ 并且大厅最初是空的。由于该排仍然可以容纳任何学生,Cordell 必须将一名学生安排在 $$$1$$$ 座位上。因此,最少就座学生人数为 $$$1$$$。

在第三个测试用例中,Cordell 可以将两名学生安排在 $$$1$$$ 和 $$$4$$$ 座位上。可以看出,她不能只放置一名学生,因此这一排不可能再容纳任何人,所以答案是 $$$2$$$。

在第四个测试用例中,无法容纳额外的学生,因此 Cordell 无法安排额外的学生,并且就座的学生数量为 $$$3$$$。