你有一张纸条,上面有一个长度为 $$$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}$$$ 的折叠不是最小长度。