题目描述

给定一个长度为 $n$ 的二进制字符串 $s$，你可以对其执行任意次数（包括零次）以下操作：

• 选择 $3$ 个下标 $1 \le i \le j \le k \le n$，对 $s_i$、$s_j$、$s_k$ 的值进行循环右移或左移。

例如，对于二进制字符串 $110110$，如果选择 $i=1$、$j=2$、$k=3$ 并进行一次循环右移，字符串变为 $011110$；如果选择 $i=4$、$j=5$、$k=6$ 并进行一次循环左移，字符串变为 $110101$。

请你计算，将给定的二进制字符串变为有序所需的最小操作次数。

注：二进制字符串指仅由字符 0 和 1 组成的字符串。

输入格式

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

每组测试用例的第一行为一个整数 $n$（$3 \le n \le 100$），表示字符串的长度。

第二行为一个长度为 $n$ 的二进制字符串 $s$。

输出格式

对于每组测试用例，输出一个整数，表示将给定二进制字符串变为有序所需的最小操作次数。

说明/提示

对于第一个测试用例，给定的字符串已经是有序的，因此不需要任何操作。

对于第二个测试用例，可以选择 $i=1$、$j=2$、$k=4$ 并进行一次循环右移。此时字符串变为 $0011$，达到了有序状态。

由 ChatGPT 5 翻译

样例

4
3
001
4
0110
6
110100
6
101011

0
1
2
1