给定一个二进制字符串 $$$S$$$,长度为 $$$n$$$,索引从 $$$1$$$ 到 $$$n$$$。您可以执行以下操作任意次数(可能为零):
- 选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$)。设 $$$cnt_0$$$ 为 $$$S[l \ldots r]$$$ 中出现 0 的次数,$$$cnt_1$$$ 为 $$$S[l \ldots r]$$$ 中出现 1 的次数。您可以支付 $$$|cnt_0 - cnt_1| + 1$$$ 硬币并对 $$$S[l \ldots r]$$$ 进行排序。 ($$$S[l \ldots r]$$$ 是指 $$$S$$$ 的子串,从位置 $$$l$$$ 开始,到位置 $$$r$$$ 结束)例如,如果 $$$S = $$$ 11001,我们可以对 $$$S[2 \ldots 4]$$$ 执行操作,支付 $$$|2 - 1| + 1 = 2$$$币,得到$$$S = $$$ 10011作为新的字符串。
求按升序对 $$$S$$$ 进行排序所需的最小硬币总数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$S$$$ 的大小。
每个测试用例的第二行包含一个二进制字符串 $$$S$$$,由 $$$n$$$ 个字符 $$$S_1S_2 \ldots S_n$$$ 组成。 (对于每个 $$$1 \le i \le n$$$,$$$S_i = $$$ 0 或 $$$S_i = $$$ 1)
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出按升序对 $$$S$$$ 进行排序所需的最小硬币总数。
示例
输入 #1
7 1 1 2 10 3 101 4 1000 5 11010 6 110000 20 01000010001010011000
输出 #1
0 1 1 3 2 2 5
注意
在第一个测试用例中,$$$S$$$ 已经排序。
在第二个测试用例中,应用 $$$l = 1, r = 2$$$ 的操作就足够了。
在第三个测试用例中,应用 $$$l = 1, r = 2$$$ 的运算就足够了。