题目描述

给你一个长度为 $N$ 的、由 $0$ 和 $1$ 构成的字符串 $S$。

你可以执行以下操作若干次：

• 选择一个整数 $1\le i\le N$，$S_i\leftarrow 1-S_i$。

你的目标是让 $S$ 中的 $1$ 连续或 $S$ 中不存在 $1$。请找出需要的最小的操作次数。

多组数据。

输入格式

多组数据。第一行一个整数 $T(1\le T\le 2\times 10^4)$，表示数据组数。

对于每组数据：
第一行一个整数 $N(1\le N\le 2\times 10^5)$。
第二行一个长为 $N$ 的字符串 $S$。$S$ 由 $0$ 和 $1$ 构成。

保证单个测试点中 $\sum N\le 2\times 10^5$。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

3
5
10011
10
1111111111
7
0000000

输出 #1

1
0
0

输入输出样例 #2

输入 #2

5
2
01
10
1000010011
12
111100010011
3
111
8
00010101

输出 #2

0
2
3
0
2

说明/提示

样例 1 解释

对于第一组数据，我们选择 $i=1$ 进行一次操作即可。

第二、三组数据不需要执行任何操作。