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

Однажды ваш друг бросил вам вызов на контест по брограммированию. На контесте по брограммированию вам дается бинарная строка$$$^{\text{∗}}$$$ $$$s$$$ длины $$$n$$$ и изначально пустая бинарная строка $$$t$$$. Во время контеста по брограммированию вы можете выполнять любые из следующих действий любое количество раз:

  • удалить некоторый суффикс$$$^{\text{†}}$$$ из $$$s$$$ и поместить его в конец $$$t$$$, или
  • удалить некоторый суффикс из $$$t$$$ и поместить его в конец $$$s$$$.
Чтобы выиграть контест по брограммированию, вы должны сделать минимальное количество операций, необходимое для того, чтобы $$$s$$$ содержала только символы $$$\texttt{0}$$$, а $$$t$$$ содержала только символы $$$\texttt{1}$$$. Найдите минимальное необходимое количество операций.

$$$^{\text{∗}}$$$Бинарная строка — это строка, состоящая из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Строка $$$a$$$ является суффиксом строки $$$b$$$, если $$$a$$$ может быть получена удалением нескольких (возможно, нуля или всех) элементов из начала $$$b$$$.

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

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

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

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$.

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

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

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

Пример
Входные данные
5
5
00110
4
1111
3
001
5
00000
3
101
Выходные данные
2
1
1
0
3
Примечание

Оптимальное решение для первого набора входных данных следующее:

  • $$$s = \texttt{00}\color{red}{\texttt{110}}$$$, $$$t =$$$ пустая строка.
  • $$$s = \texttt{00}$$$, $$$t = \texttt{11}\color{red}{\texttt{0}}$$$.
  • $$$s = \texttt{000}$$$, $$$t = \texttt{11}$$$.

Можно доказать, что нет решения, использующего менее чем $$$2$$$ операции.

Во втором наборе входных данных вам нужно переместить всю строку из $$$s$$$ в $$$t$$$ за одну операцию.

В четвертом наборе входных данных вам не нужно делать никаких операций.