← 返回题目列表

Codeforces · 1965/C

C. 折叠条

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

你有一张纸条,上面有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。您可以将纸张折叠在任意一对相邻数字之间。

如果折叠之后,位于彼此之上或之下的所有字符都相互匹配,则一组折叠被视为有效。请注意,所有折叠都是同时进行的,因此折叠之间的字符不必匹配。

例如,这些是 $$$s = \mathtt{110110110011}$$$ 和 $$$s = \mathtt{01110}$$$ 的有效折叠:

折叠条带的长度是完成所有折叠后从上方看到的长度。因此,对于上面的两个示例,在上面显示的折叠之后,长度将分别为 $$$7$$$ 和 $$$3$$$。

请注意,对于上述 $$$s = \mathtt{01110}$$$ 的折叠,如果我们单独进行这两个折叠中的任何一个,那将不是有效的折叠。但是,由于我们在完成所有折叠之前不会检查有效性,因此此折叠是有效的。

执行一组有效折叠后,您可以形成的最小长度是多少?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — 条带的大小。

每个测试用例的第二行包含一个由 $$$n$$$ 字符“0”和“1”组成的字符串 $$$s$$$ — 对条带上数字的描述。

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

输出

对于每个测试用例,输出一个整数 - 有效折叠后条带的最小可能长度。

示例

输入 #1

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

输出 #1

3
1
3
3
1
2

注意

对于第一个示例情况,一个最佳折叠是将条带从中间折叠,这样会生成长度为 3 的条带。

第三个和第四个示例情况对应于上图。请注意,上面显示的 $$$s = \mathtt{110110110011}$$$ 的折叠不是最小长度。