CF1678B2.Tokitsukaze and Good 01-String (hard version)

This is the hard version of the problem. The only difference between the two versions is that the harder version asks additionally for a minimum number of subsegments.

Tokitsukaze has a binary string $s$ of length $n$, consisting only of zeros and ones, $n$ is even.

Now Tokitsukaze divides $s$ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $s$ is considered good if the lengths of all subsegments are even.

For example, if $s$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $2$, $2$, $4$ respectively, which are all even numbers, so "11001111" is good. Another example, if $s$ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $3$, $2$, $2$, $3$. Obviously, "1110011000" is not good.

Tokitsukaze wants to make $s$ good by changing the values of some positions in $s$. Specifically, she can perform the operation any number of times: change the value of $s_i$ to '0' or '1' ($1 \leq i \leq n$). Can you tell her the minimum number of operations to make $s$ good? Meanwhile, she also wants to know the minimum number of subsegments that $s$ can be divided into among all solutions with the minimum number of operations.

这是该问题的困难版本。两个版本的唯一区别在于，困难版本额外要求子段的最少数量。

Tokitsukaze 有一个长度为 $n$ 的二进制字符串 $s$，仅由 '0' 和 '1' 构成，且 $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_i$（其中 $1 \leq i \leq n$）的值改为 '0' 或 '1'。你能告诉她使 $s$ 变为“好的”所需的最少操作次数吗？同时，在所有达到最少操作次数的方案中，她还希望知道 $s$ 所能划分出的子段的最少数量。

The first contains a single positive integer $t$ ($1 \leq t \leq 10\,000$) — the number of test cases.

For each test case, the first line contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of $s$, it is guaranteed that $n$ is even.

The second line contains a binary string $s$ of length $n$, consisting only of zeros and ones.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个正整数 $t$（$1 \leq t \leq 10\,000$）—— 表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）—— 表示字符串 $s$ 的长度，保证 $n$ 为偶数。

第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅由字符 0 和 1 组成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print a single line with two integers — the minimum number of operations to make $s$ good, and the minimum number of subsegments that $s$ can be divided into among all solutions with the minimum number of operations.

对于每个测试用例，输出一行，包含两个整数：使 $s$ 变为“好串”所需的最少操作次数，以及在所有达到最少操作次数的方案中，$s$ 能被划分成的最小子段数量。

In the first test case, one of the ways to make $s$ good is the following.

Change $s_3$, $s_6$ and $s_7$ to '0', after that $s$ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $2$ and $8$ respectively, the number of subsegments of it is $2$. There are other ways to operate $3$ times to make $s$ good, such as "1111110000", "1100001100", "1111001100", the number of subsegments of them are $2$, $4$, $4$ respectively. It's easy to find that the minimum number of subsegments among all solutions with the minimum number of operations is $2$.

In the second, third and fourth test cases, $s$ is good initially, so no operation is required.

在第一个测试用例中，使 $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$ 初始即为“好串”，因此无需任何操作。