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

Кордэл управляет рядом из $$$n$$$ мест в Scuola Comunale di Musica Piova, где студентам строго запрещено сидеть рядом друг с другом.

Вам дана бинарная строка$$$^{\text{∗}}$$$ $$$s$$$, где $$$s_i = \mathtt{1}$$$ указывает на то, что $$$i$$$-е место занято студентом, а $$$s_i = \mathtt{0}$$$ указывает на то, что оно сейчас свободно. Гарантируется, что в настоящее время никакие два соседних места не заняты. Кордэл нужно добавить больше студентов, пока невозможно будет разместить кого-либо ещё в ряду. Однако она хочет достичь этого состояния с минимальным количеством студентов.

Ваша задача — вычислить минимальное итоговое количество студентов, чтобы было невозможно разместить кого-либо ещё в ряду.

$$$^{\text{∗}}$$$Бинарная строка — это строка, в которой каждый символ является либо $$$\mathtt{0}$$$, либо $$$\mathtt{1}$$$.

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

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

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

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длиной $$$n$$$ ($$$s_i \in \{\mathtt{0}, \mathtt{1}\}$$$). Гарантируется, что нет двух подряд идущих символов $$$\mathtt{1}$$$.

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

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

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

Пример
Входные данные
5
1
0
3
000
5
00000
6
100101
13
0000100001000
Выходные данные
1
1
2
3
5
Примечание

В первом наборе входных данных $$$n = 1$$$, и зал изначально пуст. Поскольку в ряду всё ещё возможно разместить студента, Кордэл должна разместить одного студента на месте $$$1$$$. Поэтому минимальное количество сидящих студентов равно $$$1$$$.

В третьем наборе входных данных Кордэл может разместить двух студентов на местах $$$1$$$ и $$$4$$$. Можно показать, что она не может разместить только одного студента так, чтобы в ряду было невозможно разместить кого-либо ещё, поэтому ответ — $$$2$$$.

В четвёртом наборе входных данных дополнительных студентов разместить нельзя, поэтому Кордэл не размещает дополнительных студентов, и количество сидящих студентов равно $$$3$$$.