B. Постоянные изменения
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана бинарная строка $$$s$$$ длины $$$n$$$.

Строка называется чередующейся, если в ней нет двух одинаковых соседних символов. Например, 0101, 1 и 01 являются чередующимися, а 0110 — нет.

Вам нужно преобразовать $$$s$$$ в чередующуюся строку, выполнив следующую операцию любое количество раз (возможно, ноль):

  • Выберите любой символ, присутствующий в данный момент в строке, и удалите его.

Однако последовательность ваших операций должна удовлетворять правилу: удаляемые символы должны строго чередоваться. Это означает, что если последним удалённым символом был 0, то следующим удалённым символом должен быть 1, и наоборот. Самый первый удалённый символ может быть как 0, так и 1.

Найдите минимальное количество операций, необходимое для того, чтобы превратить $$$s$$$ в чередующуюся строку. Если это невозможно, выведите $$$-1$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина строки $$$s$$$.

Во второй строке каждого набора входных данных содержится бинарная строка $$$s$$$ длины $$$n$$$, состоящая из символов 0 и 1.

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

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

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

Пример
Входные данные
5
4
0101
3
111
6
100110
6
100010
6
011110
Выходные данные
0
-1
2
3
5
Примечание

В первом наборе входных данных строка 0101 уже является чередующейся. Никаких операций не требуется, поэтому ответ равен $$$0$$$.

Во втором наборе входных данных строка имеет вид 111. Чтобы сделать её чередующейся, необходимо оставить не более одного символа 1, что требует удаления двух символов 1. Однако удаления должны строго чередоваться между 0 и 1. Поскольку у нас нет 0 для удаления, выполнить два удаления невозможно. Ответ равен $$$-1$$$.

В третьем наборе входных данных строка имеет вид 100110. Мы можем просто удалить один 0 и один 1, чтобы устранить соседние дубликаты. Поскольку мы удалили ровно один 0 и один 1, операции сбалансированы и допустимы. Оставшаяся строка — 1010, что требует ровно $$$2$$$ операций.

В четвёртом наборе входных данных строка имеет вид 100010. Чтобы устранить соседние повторения, нам хотелось бы удалить два 0, чтобы получить 1010. Однако удаление двух 0 и нуля 1 нарушает правило строгого чередования (разница в количествах не может превышать $$$1$$$). Чтобы устранить этот дисбаланс, мы вынуждены дополнительно удалить один 1 с края строки. Мы удаляем два 0 и один 1 (например, в порядке 0, 1, 0), получая чередующуюся строку 010. Для этого требуется $$$3$$$ операции.

В пятом наборе входных данных строка имеет вид 011110. Для устранения соседних повторений необходимо удалить три символа 1. Чтобы сбалансировать это, мы должны дополнительно удалить как минимум два символа 0. Поскольку в нашей сжатой строке 010 есть только два символа 0 (на внешних краях), мы вынуждены удалить оба из них, в результате чего окончательная строка будет состоять только из символа 1. Мы удалили три символа 1 и два символа 0, что требует $$$5$$$ операций.