B2. Tokitsukaze и хорошая 01-строка (усложненная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это усложненная версия задачи. Единственная разница между двумя версиями состоит в том, что более сложная версия дополнительно требует минимального количества подотрезков.

У Tokitsukaze есть двоичная строка $$$s$$$ длины $$$n$$$, состоящая только из нулей и единиц, $$$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$$$ четно.

Вторая строка содержит двоичную строку $$$s$$$ длины $$$n$$$, состоящую только из нулей и единиц.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите в одной строке два целых числа — минимальное количество операций, чтобы сделать $$$s$$$ хорошей, и минимальное количество подотрезков, на которые можно разделить $$$s$$$, среди всевозможных решений, которые используют минимальное количество операций.

Пример
Входные данные
5
10
1110011000
8
11001111
2
00
2
11
6
100110
Выходные данные
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$$$ изначально хорошая, поэтому никаких действий не требуется.