题目描述

今天，Marin 正在参加一场 Cosplay 展览，并正在为一场集体合影做准备！

在合影时，Cosplayer 们会排成一条横队。如果对于每一个长度至少为 $2$ 的连续区间，男性的人数都不超过女性的人数，那么这张合影就被认为是美丽的（显然）。

目前，队伍中有 $n$ 个 Cosplayer，可以用一个二进制字符串 $s$ 描述。第 $i$ 个 Cosplayer 如果 $s_i = 0$，则为男性；如果 $s_i = 1$，则为女性。为了保证队伍美丽，你可以邀请一些额外的 Cosplayer（可以为零）加入队伍的任意位置。你不能移除任何已有的 Cosplayer。

Marin 想知道，至少需要邀请多少个 Cosplayer，才能让所有 Cosplayer 的合影变得美丽。她自己做不到，所以来请你帮忙。你能帮她吗？

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。

每个测试用例的第一行包含一个正整数 $n$（$1 \leq n \leq 100$），表示初始队伍中的 Cosplayer 数量。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，描述队伍中的 Cosplayer。字符串中的每个字符要么是 $0$（表示男性），要么是 $1$（表示女性）。

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

输出格式

对于每个测试用例，输出一个整数，表示为了让所有 Cosplayer 的合影变得美丽，至少需要邀请多少个 Cosplayer。

说明/提示

在第一个测试用例中，对于每一对相邻的 Cosplayer，你可以在他们之间各邀请两名女性 Cosplayer。这样，$000 \rightarrow 0110110$。

在第三个测试用例中，你可以在第二个 Cosplayer 旁边邀请一名女性 Cosplayer。这样，$010 \rightarrow 0110$。

由 ChatGPT 4.1 翻译

样例

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

4
2
1
0
2
0
0
0
17