← 返回题目列表

Codeforces · 2064/A

A. 编程比赛

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

醒来的一天后,你的朋友向你发起了一场编程比赛的挑战。在编程竞赛中,您将获得一个长度为 $$$n$$$ 的二进制字符串 $$$^{\text{∗}}$$$ $$$s$$$ 和一个最初为空的二进制字符串 $$$t$$$。在编程比赛期间,您可以多次执行以下任一操作:

  • 从$$$s$$$中删除一些后缀$$$^{\text{†}}$$$并将其放在$$$t$$$的末尾,或者
  • 从$$$t$$$中删除一些后缀并将其放在$$$s$$$的末尾。
要赢得编程比赛,您必须 最小值 使 $$$s$$$ 仅包含字符 $$$\texttt{0}$$$ 和 $$$t$$$ 仅包含字符 $$$\texttt{1}$$$ 所需的移动次数。找出所需的最少移动次数。

$$$^{\text{*}}$$$A 二进制字符串 是由字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 组成的字符串。

$$$^{\text{†}}$$$字符串 $$$a$$$ 是字符串 $$$b$$$ 的后缀,如果 $$$a$$$ 可以通过删除 $$$b$$$ 开头的几个(可能是零个或全部)元素来获得。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行是一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) - 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含二进制字符串$$$s$$$。

所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。

输出

对于每个测试用例,输出所需的最小移动数。

示例

输入
复制

5
5
00110
4
1111
3
001
5
00000
3
101

输出
复制

2
1
1
0
3

注意

第一个测试用例的最佳解决方案如下:

  • $$$s = \texttt{00}\color{red}{\texttt{110}}$$$,$$$t =$$$ 空字符串。
  • $$$s = \texttt{00}$$$,$$$t = \texttt{11}\color{红色}{\texttt{0}}$$$。
  • $$$s = \texttt{000}$$$,$$$t = \texttt{11}$$$。

可以证明,不存在使用少于 $$$2$$$ 步数的解决方案。

在第二个测试用例中,您必须一次性将整个字符串从 $$$s$$$ 移动到 $$$t$$$。

在第四个测试用例中,您不必执行任何操作。