给你一个长度为 $$$n$$$ 的字符串 $$$s$$$。字符串 $$$s$$$ 是二进制的,换句话说,仅由 0 和 1 组成。
字符串 $$$s$$$ 恰好有 $$$\frac{n}{2}$$$ 零和 $$$\frac{n}{2}$$$ 个($$$n$$$ 是偶数)。
在一次操作中,您可以反转 $$$s$$$ 的任何子字符串。字符串的子字符串是该字符串的连续子序列。
使字符串$$$s$$$交替需要最少多少次操作?如果对于所有 $$$i$$$,$$$s_i \neq s_{i + 1}$$$ 则字符串是交替的。交替字符串一般有两种类型:01010101...或10101010...
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$;$$$n$$$ 是偶数)——字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ ($$$s_i \in$$$ {0, 1})。字符串 $$$s$$$ 恰好有 $$$\frac{n}{2}$$$ 零和 $$$\frac{n}{2}$$$ 。
保证测试用例$$$n$$$的总和不超过$$$10^5$$$。
输出
对于每个测试用例,打印使 $$$s$$$ 交替的最小操作数。
示例
输入 #1
3 2 10 4 0110 8 11101000
输出 #1
0 1 2
注意
在第一个测试用例中,字符串 10 已经是交替的。
在第二个测试用例中,例如,我们可以反转 $$$s$$$ 的最后两个元素并得到:0110 $$$\rightarrow$$$ 0101。
在第三个测试用例中,我们可以例如进行以下两个操作:
1. 11101000 $$$\rightarrow$$$ 10101100;
2. 10101100 $$$\rightarrow$$$ 10101010。