给定一个长度为 $n$ 的二进制字符串 $s$（仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成）。

你可以进行任意次数操作（包括不操作）： 选取三个下标满足 $1\le i<j<k\le n$，对 $s_i,s_j,s_k$ 进行循环右移或循环左移。

举例说明： 二进制字符串 $\texttt{110110}$：

1. 选取 $i=1,j=2,k=3$ 做循环右移，字符串变为 $\texttt{011110}$；
2. 选取 $i=4,j=5,k=6$ 做循环左移，字符串变为 $\texttt{110101}$。

求将给定二进制字符串排成非递减有序（所有$\texttt{0}$在前、$\texttt{1}$在后）所需的最少操作次数。

输入格式

多组测试数据。 第一行一个整数 $t$（$1\le t\le 100$），表示测试用例组数。

每组测试用例： 第一行输入整数 $n$（$3\le n\le 100$），代表字符串长度。 第二行输入长度为 $n$ 的二进制字符串 $s$。

输出格式

对每组测试用例，输出一个整数：将字符串排序所需的最少操作次数。

样例输入

4
3
001
4
0110
6
110100
6
101011

样例输出

0
1
2
1

样例说明

1. 第一组：字符串已经有序，无需操作，答案为 $0$。
2. 第二组：选取 $i=1,j=2,k=4$ 执行一次循环右移，即可变为有序串 $\texttt{0011}$，答案为 $1$。

补充术语注释

• binary string：二进制字符串，仅由 $\texttt{0},\texttt{1}$ 构成
• cyclically left shift：循环左移
• cyclically right shift：循环右移
• sorted binary string：有序二进制串，规范形态为所有$\texttt{0}$排在前面，所有$\texttt{1}$排在后面