← 返回题目列表

Codeforces · 1658/A

A. 马林和拍摄照片

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

今天,马林正在参加cosplay展,正在准备拍摄集体照!

在集体照中,coser 们排成一条水平线。如果对于至少 $$$2$$$ 角色扮演者的每个连续片段,男性数量不超过女性数量(显然),则集体照片被认为是美丽的。

目前,该线路有 $$$n$$$ 个角色扮演者,可以用二进制字符串 $$$s$$$ 来描述。如果 $$$s_i = 0$$$,则第 $$$i$$$ 角色扮演者为男性;如果 $$$s_i = 1$$$,则为女性。为了保证队伍美观,你可以在任意位置邀请一些额外的coser(可能是零)加入队伍。您无法从队列中删除任何角色扮演者。

马林想知道你需要邀请的最少人数的角色扮演者,以便所有角色扮演者的合影都很漂亮。她自己无法做到这一点,所以她向你寻求帮助。你能帮助她吗?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 第一行中角色扮演者的数量。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ — 描述已经排队的角色扮演者。字符串中的每个字符要么是 0 描述男性,要么是 1 描述女性。

请注意,$$$n$$$ 的总和没有限制。

输出

对于每个测试用例,打印您需要邀请的最少角色扮演者数量,以便所有角色扮演者的合影都很漂亮。

示例

输入 #1

9
3
000
3
001
3
010
3
011
3
100
3
101
3
110
3
111
19
1010110000100000101

输出 #1

4
2
1
0
2
0
0
0
17

注意

在第一个测试用例中,对于每对相邻的角色扮演者,您可以邀请两名女性角色扮演者站在他们之间。然后,$$$000 \rightarrow 0110110$$$。

在第三个测试用例中,您可以邀请一名女性角色扮演者站在第二个角色扮演者旁边。然后,$$$010 \rightarrow 0110$$$。