A. Марин и фотосессия
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня Марин пришла на фестиваль косплея и готовится к групповому фотоснимку!

Для группового снимка косплееры выстраиваются в горизонтальный ряд. Групповой снимок считается красивым, если на каждом непрерывном отрезке, включающем хотя бы $$$2$$$ косплееров, количество мужчин не превышает количества женщин (очевидно).

Сейчас ряд состоит из $$$n$$$ косплееров и может быть описан бинарной строкой $$$s$$$. $$$i$$$-й косплеер — мужчина, если $$$s_i = 0$$$, а женщина, если $$$s_i = 1$$$. Чтобы сделать ряд красивым, вы можете предложить дополнительным косплеерам (возможно, нулю) встать в любое место в ряду. Вы не можете исключать косплееров из ряда.

Марин хочет узнать минимальное количество дополнительных косплееров, которых нужно пригласить, чтобы групповой снимок получился красивым. Она не может сделать это сама, поэтому просит у вас помощи. Сможете ей помочь?

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое положительное число $$$n$$$ ($$$1 \leq n \leq 100$$$) — начальное количество косплееров в ряду.

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

Обратите внимание, что ограничений на сумму $$$n$$$ по всем наборам нет.

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

Для каждого набора входных данных выведите минимальное количество косплееров, которых нужно добавить в ряд, чтобы фото стало красивым.

Пример
Входные данные
9
3
000
3
001
3
010
3
011
3
100
3
101
3
110
3
111
19
1010110000100000101
Выходные данные
4
2
1
0
2
0
0
0
17
Примечание

В первом примере для каждой пары подряд стоящих косплееров вы можете пригласить двух девушек-косплееров для того, чтобы они встали между ними. Тогда $$$000 \rightarrow 0110110$$$.

В третьем наборе вы можете пригласить одну девушку-косплеера, чтобы она встала после второго косплеера. Тогда $$$010 \rightarrow 0110$$$.