B2. Tokitsukaze and Good 01-String (hard version)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis 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.InputThe 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.OutputFor 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.ExampleInput
5
10
1110011000
8
11001111
2
00
2
11
6
100110
Output
3 2
0 3
0 1
0 1
3 1
NoteIn 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.
5
10
1110011000
8
11001111
2
00
2
11
6
100110

3 2 0 3 0 1 0 1 3 1 
['dp', 'greedy', 'implementation', '*1800']