CF1658A.Marin and Photoshoot

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?

今天，马林正在参加一场动漫角色扮演展览，并准备进行团体合影！

在团体照中，角色扮演者排成一条水平线。如果对于每一个长度至少为 $2$ 的连续子段，男性人数都不超过女性人数，则该团体照被认为是“美丽的”（显然如此）。

目前，这条队伍中有 $n$ 位角色扮演者，可用一个二进制字符串 $s$ 来描述：第 $i$ 位角色扮演者为男性当且仅当 $s_i = 0$，为女性当且仅当 $s_i = 1$。为了确保整条队伍满足“美丽”的条件，你可以邀请若干额外的角色扮演者（可以为零个）插入到队伍中的任意位置。但你不能从队伍中移除任何已有角色扮演者。

马林想知道：为使所有角色扮演者的团体照变得“美丽”，你最少需要邀请多少位新角色扮演者？她自己无法解决这个问题，因此向你求助。你能帮帮她吗？

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$.

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

每个测试用例的第一行包含一个正整数 $n$（$1 \leq n \leq 100$）—— 表示初始队列中角色扮演者的数量。

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

注意：所有测试用例的 $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.

对于每个测试用例，输出你需要邀请的最小 cosplay 者人数，使得所有 cosplay 者的合影是美丽的。

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$.

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

在第三个测试用例中，你可以邀请一名女性扮演者站在第二个扮演者旁边。于是，$010 \rightarrow 0110$。