给你一个长度为$$$n$$$的二进制字符串$$$^{\text{*}}$$$ $$$s$$$,并且允许你执行以下操作任意次数(包括零次):
- 选择 $$$3$$$ 索引 $$$1 \le i \lt j \lt k \le n$$$ 并循环右移或左移 $$$s_i$$$、$$$s_j$$$、$$$s_k$$$ 上的值。
对于二进制字符串 110110,如果我们选择 $$$i=1$$$, $$$j=2$$$, $$$k=3$$$ 并循环右移,则字符串变为 011110;如果我们选择 $$$i=4$$$, $$$j=5$$$, $$$k=6$$$ 并循环执行左移,则字符串变为 110101.
确定对给定二进制字符串进行排序所需的最少操作数。
$$$^{\text{*}}$$$A 二进制字符串 是一个仅由字符组成的字符串 0 和 1.
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 100$$$) — 字符串的长度。
第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$。
输出
对于每个测试用例,输出一个整数 - 对给定二进制字符串进行排序所需的最少操作数。
示例
输入复制
430014011061101006101011
输出复制
0 1 2 1
注意
对于第一个测试用例,给定的字符串已经排序。因此,不需要进行任何操作。
对于第二个测试用例,我们可以选择 $$$i = 1$$$, $$$j = 2$$$, $$$k = 4$$$ 并循环执行右移。该字符串变为等于 0011,已排序。