CF2241C.RemovevomeR

You are given a binary string $s$ consisting only of the characters $\texttt{0}$ and $\texttt{1}$.

In one operation, you can do the following:

• Choose a substring$^{\text{∗}}$ of $s$ that is a palindrome$^{\text{†}}$ of length at least $2$.
• Delete exactly one character from this chosen substring.

The remaining parts of the string are then concatenated to form the new string $s$.

Find the minimum possible length of the string $s$ that can be achieved after applying this operation any number of times (possibly zero).

$^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$^{\text{†}}$A string $a$ of length $m$ is said to be palindrome if $a_i = a_{m + 1 - i}$ for all $1 \le i \le m$.

给你一个仅由字符 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$ 是一个回文串。

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Description of each test case follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the length of the binary string $s$.

The second line of each test case contains a binary string $s$ of length $n$. It is guaranteed that each character of $s$ is either $\texttt{0}$ or $\texttt{1}$.

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

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

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

For each test case, print the minimum possible length of the string $s$ that can be achieved after applying the operation any number of times.

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

In the first test case, the initial string is $\texttt{0000}$. We can perform the following sequence of operations:

• Choose the palindromic substring $\texttt{0000}$. Delete one $\texttt{0}$. The string becomes $\texttt{000}$.
• Choose the palindromic substring $\texttt{000}$. Delete one $\texttt{0}$. The string becomes $\texttt{00}$.
• Choose the palindromic substring $\texttt{00}$. Delete one $\texttt{0}$. The string becomes $\texttt{0}$.

The string $\texttt{0}$ contains no palindromic substrings of length at least $2$, so no further operations can be performed. The minimum possible length is $1$.

In the second test case, the initial string is $\texttt{110}$.

• Choose the palindromic substring $\texttt{11}$. Delete one $\texttt{1}$. The string becomes $\texttt{10}$.

The string $\texttt{10}$ contains no palindromic substrings of length at least $2$, so no further operations can be performed. The minimum possible length is $2$.

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