这是问题的困难版本。两个版本之间的唯一区别是,较难的版本还额外要求最小数量的子段。
Tokitsukaze 有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅由零和一组成,$$$n$$$ 是偶数。
现在Tokitsukaze将$$$s$$$划分为最小数量的连续子段,并且对于每个子段,每个子段中的所有位都是相同的。之后,如果所有子段的长度都是偶数,则 $$$s$$$ 被认为是好的。
例如,如果$$$s$$$是“11001111”,它将被分为“11”、“00”和“1111”。它们的长度分别是$$$2$$$、$$$2$$$、$$$4$$$,都是偶数,所以“11001111”是好的。再比如$$$s$$$为“1110011000”,则会分为“111”、“00”、“11”、“000”,它们的长度分别为$$$3$$$、$$$2$$$、$$$2$$$、$$$3$$$。显然,“1110011000”不好。
Tokitsukaze 希望通过更改 $$$s$$$ 中某些位置的值来使 $$$s$$$ 变得更好。具体来说,她可以多次执行该操作:将 $$$s_i$$$ 的值更改为“0”或“1”($$$1 \leq i \leq n$$$)。你能告诉她最少需要多少次操作才能使 $$$s$$$ 变得良好吗?同时,她还想知道$$$s$$$在所有解中以最少的操作数可以划分出最少的子段数。
输入
第一个包含一个正整数 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — 测试用例的数量。
对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — $$$s$$$ 的长度,保证 $$$n$$$ 是偶数。
第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅由零和一组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一行包含两个整数 - 使 $$$s$$$ 良好的最小操作数,以及 $$$s$$$ 在具有最少操作数的所有解决方案中可以划分的最小子段数。
示例
输入 #1
5 10 1110011000 8 11001111 2 00 2 11 6 100110
输出 #1
3 2 0 3 0 1 0 1 3 1
注意
在第一个测试用例中,使 $$$s$$$ 变得良好的方法之一如下。
将$$$s_3$$$、$$$s_6$$$和$$$s_7$$$改为'0',则$$$s$$$变为“1100000000”,可分为“11”和“00000000”,长度分别为$$$2$$$和$$$8$$$,个数它的子段是$$$2$$$。还有其他方法可以操作$$$3$$$次来使$$$s$$$变好,例如“1111110000”、“1100001100”、“1111001100”,它们的子段数分别为$$$2$$$、$$$4$$$、$$$4$$$。不难发现,所有运算次数最少的方案中,子段的数量最少为$$$2$$$。
在第二个、第三个和第四个测试用例中,$$$s$$$ 最初是好的,所以不需要任何操作。