醒来的一天后,你的朋友向你发起了一场编程比赛的挑战。在编程竞赛中,您将获得一个长度为 $$$n$$$ 的二进制字符串 $$$^{\text{∗}}$$$ $$$s$$$ 和一个最初为空的二进制字符串 $$$t$$$。在编程比赛期间,您可以多次执行以下任一操作:
- 从$$$s$$$中删除一些后缀$$$^{\text{†}}$$$并将其放在$$$t$$$的末尾,或者
- 从$$$t$$$中删除一些后缀并将其放在$$$s$$$的末尾。
$$$^{\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$$$。
输出
对于每个测试用例,输出所需的最小移动数。
示例
输入复制
55001104111130015000003101
输出复制
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$$$。
在第四个测试用例中,您不必执行任何操作。