题目描述

某天你醒来后，朋友向你发起了兄弟编程比赛的挑战。在兄弟编程比赛中，你会得到一个长度为 $n$ 的二进制字符串 $^{\text{∗}}$ $s$ 和一个初始为空的二进制字符串 $t$。在比赛过程中，你可以执行以下任意操作任意次数：

• 从 $s$ 中移除某个后缀 $^{\text{†}}$ 并将其添加到 $t$ 的末尾，或
• 从 $t$ 中移除某个后缀并将其添加到 $s$ 的末尾。

为了赢得比赛，你必须使用最少次数的操作使得 $s$ 仅包含字符 $\texttt{0}$ 且 $t$ 仅包含字符 $\texttt{1}$。请找出所需的最少操作次数。

$^{\text{∗}}$ 二进制字符串是仅由字符 $\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$。

输出格式

对于每个测试用例，输出所需的最少操作次数。

说明/提示

第一个测试用例的最优解如下：

1. $s = \texttt{00}\color{red}{\texttt{110}}$，$t =$ 空字符串。
2. 将 $\texttt{110}$ 从 $s$ 移动到 $t$：$s = \texttt{00}$，$t = \texttt{110}$。
3. 将 $\texttt{0}$ 从 $t$ 移回 $s$：$s = \texttt{000}$，$t = \texttt{11}$。

可以证明无法用少于 $2$ 次操作完成。

第二个测试用例中，必须用一次操作将整个字符串从 $s$ 移动到 $t$。

第四个测试用例中，无需任何操作。

翻译由 DeepSeek R1 完成

样例

5
5
00110
4
1111
3
001
5
00000
3
101

2
1
1
0
3