← 返回题目列表

Codeforces · 2241/C

C. 删除 vomeR

中文机器翻译题面 查看原题

给定一个二进制字符串 $$$s$$$,仅包含字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$。

在一次操作中,您可以执行以下操作:

  • 选择 $$$s$$$ 中的一个子串 $$$^{\text{*}}$$$,它是长度至少为 $$$2$$$ 的回文 $$$^{\text{†}}$$$。
  • 从所选子字符串中删除一个字符。

然后将字符串的其余部分连接起来形成新字符串 $$$s$$$。

找出在应用此操作任意次数(可能为零)后可以达到的字符串 $$$s$$$ 的最小可能长度。

$$$^{\text{*}}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

$$$^{\text{†}}$$$如果对于所有 $$$1 \le i \le m$$$,$$$a_i = a_{m + 1 - i}$$$,则长度为 $$$m$$$ 的字符串 $$$a$$$ 被称为回文。

输入

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

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

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

输出

对于每个测试用例,打印应用任意次操作后可以达到的字符串 $$$s$$$ 的最小可能长度。

示例

输入
复制

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$$$。