折叠纸条

单个测试用例时间限制：$2$ 秒 内存限制：$256$ 兆字节

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

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

例如，以下是对 $s=110110110011$ 和 $s=01110$ 的合法折叠方式：

折叠后纸条的长度，是从上方看过去的可见长度。例如上面两个例子，折叠后的长度分别为 $7$ 和 $3$。

注意：对于上面 $s=01110$ 的折叠方式，如果只单独做其中某一个折叠，折叠方式是不合法的。但因为我们只在全部折叠完成后才检查合法性，所以这组折叠是合法的。

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

输入格式

第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。

每个测试用例的描述如下：

• 第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），表示纸条长度。
• 第二行包含一个由字符 0 和 1 组成的字符串 $s$，表示纸条上的内容。

保证所有测试用例的 $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=110110110011$ 的折叠方式并不是最短长度的方案。