← 返回题目列表

Codeforces · 2140/A

A. 移位排序

中文机器翻译题面 查看原题

给你一个长度为$$$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$$$。

输出

对于每个测试用例,输出一个整数 - 对给定二进制字符串进行排序所需的最少操作数。

示例

输入
复制

4
3
001
4
0110
6
110100
6
101011

输出
复制

0
1
2
1

注意

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

对于第二个测试用例,我们可以选择 $$$i = 1$$$, $$$j = 2$$$, $$$k = 4$$$ 并循环执行右移。该字符串变为等于 0011,已排序。