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

Вам задана строка $$$s$$$ четной длины $$$n$$$. Строка $$$s$$$ — бинарная, другими словами, состоит только из 0 (нулей) и 1 (единиц).

Строка $$$s$$$ состоит ровно из $$$\frac{n}{2}$$$ нулей и $$$\frac{n}{2}$$$ единиц ($$$n$$$ — четное).

За одну операцию вы можете развернуть любую подстроку $$$s$$$. Подстрока строки — это непрерывная подпоследовательность символов данной строки.

Какое минимальное количество операций вам понадобится, чтобы сделать $$$s$$$ чередующейся? Строка чередующаяся, если $$$s_i \neq s_{i + 1}$$$ для всех $$$i$$$. В общем, существует два типа чередующихся строк: 01010101... или 10101010...

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

В первой строке задано единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

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

Во второй строке каждого набора задана бинарная строка $$$s$$$ длины $$$n$$$ ($$$s_i \in$$$ {0, 1}). В строке $$$s$$$ ровно $$$\frac{n}{2}$$$ нулей и $$$\frac{n}{2}$$$ единиц.

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

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

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

Пример
Входные данные
3
2
10
4
0110
8
11101000
Выходные данные
0
1
2
Примечание

В первом наборе входных данных, строка 10 уже чередующаяся.

Во втором наборе, мы можем, например, развернуть два последних символа $$$s$$$ и получить: 0110 $$$\rightarrow$$$ 0101.

В третьем наборе, мы можем, например, сделать следующие две операции:

  1. 11101000 $$$\rightarrow$$$ 10101100;
  2. 10101100 $$$\rightarrow$$$ 10101010.