分数：

400 分

问题陈述

给定一个长度为 $N$ 的字符串 $S$，该字符串仅由字符 0 和 1 组成。

您可以执行任意多次（包括零次）以下操作：

选择一个整数 $i$，满足 $1 \leq i \leq N$，并将 $S$ 中第 $i$ 个位置的字符从 0 变为 1，或者从 1 变为 0。

您的目标是通过这些操作使得字符串 $S$ 中的所有 1 形成至多一个连续区间。请找出实现该目标所需的最小操作次数。

更具体地说，目标是使字符串 $S$ 满足以下条件：存在一对整数 $(l, r)$，满足：

$1 \leq l \leq r \leq N + 1$

对于每个 $1 \leq i \leq N$，如果 $S_i = 1$，则 $l \leq i < r$

可以证明，该目标总是可以通过有限次操作实现。

共有 $T$ 个测试用例，您需要分别解决每个测试用例。

约束条件

$1 \leq T \leq 20000$

$1 \leq N \leq 2 \times 10^5$

$S$ 是一个长度为 $N$ 的字符串，仅由字符 0 和 1 组成。

对于每个输入文件，所有测试用例中 $N$ 的总和最多为 $2 \times 10^5$。

$T$ 和 $N$ 均为整数。

输入

输入从标准输入中按以下格式给出：

第一行包含一个整数 $T$，表示测试用例的数量。

接下来的 $T$ 行，每行描述一个测试用例，格式如下：

第一行包含一个整数 $N$，表示字符串 $S$ 的长度。

第二行包含字符串 $S$。

输出

输出 $T$ 行，每行包含一个整数，表示对应测试用例的最小操作次数。

样例输入 1

3 5 10011 10 1111111111 7 0000000

样例输出 1

1 0 0

解释：

第一个测试用例：如果将 $S_1$ 从 1 变为 0，字符串变为 "00011"，此时所有 1 形成一个区间 [3, 4]。初始字符串不满足条件，因此需要进行一次操作，答案为 1。

第二个测试用例：字符串中没有 0，所有 1 已经形成一个区间，不需要任何操作，答案为 0。

第三个测试用例：字符串中没有 1，自然满足条件，不需要任何操作，答案为 0。

样例输入 2

5 2 01 10 1000010011 12 111100010011 3 111 8 00010101

样例输出 2

0 2 3 0 2

希望这个翻译更加清晰和准确！如果还有其他需要翻译或解释的部分，请随时告诉我。

fjt>-ctj