给定一个二进制字符串 $$$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$$$ 的最小可能长度。
示例
输入复制
440000311061100116101100
输出复制
1211
注意
在第一个测试用例中,初始字符串是 $$$\texttt{0000}$$$。我们可以执行以下操作序列:
- 选择回文子字符串 $$$\texttt{0000}$$$。删除一个$$$\texttt{0}$$$。该字符串变为 $$$\texttt{000}$$$。
- 选择回文子字符串 $$$\texttt{000}$$$。删除一个$$$\texttt{0}$$$。该字符串变为 $$$\texttt{00}$$$。
- 选择回文子字符串 $$$\texttt{00}$$$。删除一个$$$\texttt{0}$$$。该字符串变为 $$$\texttt{0}$$$。
在第二个测试用例中,初始字符串是 $$$\texttt{110}$$$。
- 选择回文子字符串 $$$\texttt{11}$$$。删除一个$$$\texttt{1}$$$。该字符串变为 $$$\texttt{10}$$$。