Marin and Photoshoot

题意翻译

我们称一个仅包含字符 `0` 和 `1` 的字符串是美丽的，当且仅当对于其所有长度 $\geqslant 2$ 的子串，都满足当中 `0` 的个数不超过 `1` 的个数。 现在，给定一个长度为 $n$ 且仅包含字符 `0` 和 `1` 的字符串 $s$，你可以在该字符串的任意位置插入字符 `0` 或 `1`。求使得字符串 $s$ 是美丽的，至少要插入多少个字符。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^3$。 - $1\leqslant n\leqslant 100$。 Translated by Eason_AC

题目描述

Today, Marin is at a cosplay exhibition and is preparing for a group photoshoot! For the group picture, the cosplayers form a horizontal line. A group picture is considered beautiful if for every contiguous segment of at least $ 2 $ cosplayers, the number of males does not exceed the number of females (obviously). Currently, the line has $ n $ cosplayers which can be described by a binary string $ s $ . The $ i $ -th cosplayer is male if $ s_i = 0 $ and female if $ s_i = 1 $ . To ensure that the line is beautiful, you can invite some additional cosplayers (possibly zero) to join the line at any position. You can't remove any cosplayer from the line. Marin wants to know the minimum number of cosplayers you need to invite so that the group picture of all the cosplayers is beautiful. She can't do this on her own, so she's asking you for help. Can you help her?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^3 $ ) — the number of test cases. The first line of each test case contains a positive integer $ n $ ( $ 1 \leq n \leq 100 $ ) — the number of cosplayers in the initial line. The second line of each test case contains a binary string $ s $ of length $ n $ — describing the cosplayers already in line. Each character of the string is either 0 describing a male, or 1 describing a female. Note that there is no limit on the sum of $ n $ .

输出格式

For each test case, print the minimum number of cosplayers you need to invite so that the group picture of all the cosplayers is beautiful.

输入输出样例

输入样例 #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

说明

In the first test case, for each pair of adjacent cosplayers, you can invite two female cosplayers to stand in between them. Then, $ 000 \rightarrow 0110110 $ . In the third test case, you can invite one female cosplayer to stand next to the second cosplayer. Then, $ 010 \rightarrow 0110 $ .