CF2241C.RemovevomeR

给你一个仅由字符 0 和 1 组成的二进制字符串 $s$。

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

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

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

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

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

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

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

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

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

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

在第一个测试用例中，初始字符串为 $\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$。