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

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

  • Выберите $$$3$$$ индекса $$$1 \le i \lt j \lt k \le n$$$ и циклически сдвиньте значения $$$s_i$$$, $$$s_j$$$, $$$s_k$$$ вправо или влево.

Например, для бинарной строки 110110, если мы выберем $$$i=1$$$, $$$j=2$$$, $$$k=3$$$ и выполним циклический сдвиг вправо, строка станет 011110; если мы выберем $$$i=4$$$, $$$j=5$$$, $$$k=6$$$ и выполним циклический сдвиг влево, строка станет 110101.

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

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

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

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

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

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

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

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

Пример
Входные данные
4
3
001
4
0110
6
110100
6
101011
Выходные данные
0
1
2
1
Примечание

Для первого набора входных данных данная строка уже отсортирована. Таким образом, операции не требуются.

Для второго набора входных данных мы можем выбрать $$$i = 1$$$, $$$j = 2$$$, $$$k = 4$$$ и выполнить циклический сдвиг вправо. Строка станет равна 0011, что является отсортированной строкой.