题目描述

江桥定义一个只由字符 0 和 1 组成的字符串为 “茳峤串” 当且仅当其包含 至少 $3$ 个 $\texttt{"01"}$ 或 $\texttt{"10"}$ 子串。

例如 $\texttt{"11010100"},\texttt{"00110011"}$ 都是“茳峤串”，而 $\texttt{"001110"},\texttt{"1111111"}$ 则不是，因为前者只包含一个 $\texttt{"01"}$ 和一个 $\texttt{"10"}$ 总共两个这样的子串，而后者一个这样的子串都没有。

江桥现在得到了一个只包含 0 和 1 的字符串 $s$。

现在，江桥进行任意次（包括 $0$ 次）以下操作：

花费 $1$ 的代价，将字符串中的任意一个字符反转（即 $0$ 变为 $1$，$1$ 变为 $0$）

江桥至少要花费多少代价，才能将字符串变为“茳峤串“？

容易证明，在 $n\geq 4$ 的情况下一定存在合法的操作方式。

输入格式

输入包含多组数据。第一行一个正整数 $T$，表示数据组数。对于每组数据：

第一行一个正整数 $n$，表示字符串长度。

第二行一个长度为 $n$ 的字符串 $s$，含义如上所述。

输出格式

一个非负整数代表江桥至少要花费多少代价，才能将字符串变为“茳峤串”。

5
4
1100
4
0101
4
0110
4
0111
4
0000

2
0
2
1
2

样例解释

对于第一组数据，只需要花费 $2$ 的代价把第二个字符变成 0，并把第三个字符变成 1 即可。

数据规模与约定

下发文件

下发文件对应子任务 $1$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10^4,4 \leq n,\sum n \leq 10^{6},|s|=n,s_i\in\{'0','1'\}$。