当前没有测试数据。

CF测试跳转：https://codeforces.com/contest/2241/problem/C

给定一个仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成的二进制字符串 $s$。

在一次操作中，你可以执行以下步骤：

• 选择 $s$ 的一个子串$^{\text{∗}}$，该子串是一个长度至少为 $2$ 的回文串$^{\text{†}}$。
• 从该选定的子串中恰好删除一个字符。

字符串的剩余部分随后被拼接起来，形成新的字符串 $s$。

找出经过任意次（可能为零次）操作后，字符串 $s$ 可能达到的最小长度。

$^{\text{∗}}$ 如果可以通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符，并从结尾删除若干（可能为零或全部）字符得到字符串 $a$，则称 $a$ 是 $b$ 的子串。

$^{\text{†}}$ 如果一个长度为 $m$ 的字符串 $a$ 满足对于所有 $1 \le i \le m$ 都有 $a_i = a_{m + 1 - i}$，则称该字符串为回文串。

输入

第一行包含一个整数 $t$（$1 \le t \le 100$）——测试用例的数量。每个测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）——二进制字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。保证 $s$ 中的每个字符都是 $\texttt{0}$ 或 $\texttt{1}$。

输出

对于每个测试用例，输出经过任意次操作后字符串 $s$ 可能达到的最小长度。

Example

4
4
0000
3
110
6
110011
6
101100

1
2
1
1

注意

在第一个测试用例中，初始字符串为 $\texttt{0000}$。我们可以执行以下操作序列：

• 选择回文子串 $\texttt{0000}$。删除一个 $\texttt{0}$。字符串变为 $\texttt{000}$。
• 选择回文子串 $\texttt{000}$。删除一个 $\texttt{0}$。字符串变为 $\texttt{00}$。
• 选择回文子串 $\texttt{00}$。删除一个 $\texttt{0}$。字符串变为 $\texttt{0}$。

字符串 $\texttt{0}$ 不包含长度至少为 $2$ 的回文子串，因此无法进行进一步操作。最小可能长度为 $1$。

在第二个测试用例中，初始字符串为 $\texttt{110}$。

• 选择回文子串 $\texttt{11}$。删除一个 $\texttt{1}$。字符串变为 $\texttt{10}$。

字符串 $\texttt{10}$ 不包含长度至少为 $2$ 的回文子串，因此无法进行进一步操作。最小可能长度为 $2$。