您有一个由 $$$n$$$ 个字符组成的字符串 $$$s$$$。每个字符要么是 0,要么是 1。
您可以对字符串执行操作。每个操作由两个步骤组成:
1、从$$$1$$$中选择一个整数$$$i$$$到字符串$$$s$$$的长度,然后删除字符$$$s_i$$$(字符串长度减少$$$1$$$,删除的字符右边的字符索引也减少$$$1$$$);
2. 如果字符串$$$s$$$不为空,则删除由相同字符组成的最大长度前缀(剩余字符的索引和字符串长度减去删除的前缀的长度)。
请注意,这两个步骤在每个操作中都是强制性的,并且它们的顺序不能更改。
例如,如果您有字符串 $$$s =$$$ 111010,则第一个操作可以是以下操作之一:
1. 选择 $$$i = 1$$$: 我们将得到 111010 $$$\rightarrow$$$ 11010 $$$\rightarrow$$$ 010;
2. 选择 $$$i = 2$$$: 我们将得到 111010 $$$\rightarrow$$$ 11010 $$$\rightarrow$$$ 010;
3. 选择 $$$i = 3$$$: 我们将得到 111010 $$$\rightarrow$$$ 11010 $$$\rightarrow$$$ 010;
4. 选择 $$$i = 4$$$: 我们将得到 111010 $$$\rightarrow$$$ 11110 $$$\rightarrow$$$ 0;
5. 选择 $$$i = 5$$$: 我们将得到 111010 $$$\rightarrow$$$ 11100 $$$\rightarrow$$$ 00;
6. 选择 $$$i = 6$$$:我们将得到 111010 $$$\rightarrow$$$ 11101 $$$\rightarrow$$$ 01。
当字符串 $$$s$$$ 变空时,您完成执行操作。您最多可以执行多少次操作?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。
第二行包含 $$$s$$$ 个字符的字符串 $$$n$$$。每个字符要么是 0,要么是 1。
保证测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 您可以执行的最大操作数。
示例
输入 #1
5 6 111010 1 0 1 1 2 11 6 101010
输出 #1
3 1 1 1 3
注意
在第一个测试用例中,您可以选择 $$$i = 2$$$ 并在第一次操作后获取字符串 010。之后,您可以选择$$$i = 3$$$并获取字符串1。最后,您只能选择$$$i = 1$$$并获取空字符串。