题目描述

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

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

• 选择 $s$ 中一个长度至少为 $2$ 的回文子串。
• 从这个被选定的子串中恰好删除一个字符。
• 剩余的部分将拼接起来形成新的字符串 $s$。

请找出在执行上述操作任意次数（包括 $0$ 次）后，字符串 $s$ 所能达到的最小可能长度。

子串是指通过从原字符串的开头和/或结尾删除若干（可能为零或全部）个字符所得到的字符串。

回文串是指一个长度为 $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$ 的每个字符要么是 0，要么是 1。

输出格式

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

样例输入 1

4
4
0000
3
110
6
110011
6
101100

样例输出 1

1
2
1
1

说明

样例解释

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

  1. 选择回文子串 0000。删除一个 0。字符串变为 000。
  2. 选择回文子串 000。删除一个 0。字符串变为 00。
  3. 选择回文子串 00。删除一个 0。字符串变为 0。 字符串 0 中不包含任何长度至少为 $2$ 的回文子串，因此无法继续进行操作。最小可能长度为 $1$。

• 在第二个测试用例中，初始字符串为 110。

  1. 选择回文子串 11。删除一个 1。字符串变为 10。 字符串 10 中不包含任何长度至少为 $2$ 的回文子串，因此无法继续进行操作。最小可能长度为 $2$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 100$。
• 对于每个测试用例，保证 $1 \le n \le 100$。
• 保证所有的输入数值均为整数。