E. 折叠纸条

单点时限：2 秒 内存限制：256 MB

你有一张纸条，上面写着长度为 $n$ 的二进制字符串 $s$。你可以在任意两个相邻字符之间折叠这张纸条。

如果在完成所有折叠后，所有上下重叠在一起的字符都相同，那么这组折叠方式被称为合法的。注意：所有折叠是同时完成的，因此在折叠过程中不需要满足字符匹配。

例如，下面是对 $s=\texttt{110110110011}$ 和 $s=\texttt{01110}$ 的合法折叠方式：

折叠后纸条的长度，是从上方俯视时看到的长度。例如上面两个例子折叠后的长度分别为 $7$ 和 $3$。

注意：对于上面 $s=\texttt{01110}$ 的折叠方式，如果只做其中某一次折叠，结果是不合法的。但因为我们在所有折叠完成后才检查合法性，所以这种整体折叠是合法的。

在执行一组合法折叠后，你能得到的纸条的最小可能长度是多少？

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$）—— 测试用例数量。 每个测试用例的描述如下：

第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$）—— 纸条长度。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 合法折叠后纸条的最小可能长度。

样例输入

6
6
101101
1
0
12
110110110011
5
01110
4
1111
2
01

样例输出

3
1
3
3
1
2

样例说明

对于第一个样例，最优方式是在中间折叠，得到长度为 $3$ 的纸条。 第三个和第四个样例对应题目描述中的图示。注意：图中对 $s=\texttt{110110110011}$ 的折叠方式并不是最短的。