C. И, ИЛИ, сортировка!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана двоичная строка$$$^{\text{∗}}$$$ $$$s$$$ длины $$$n$$$.

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

Обратите внимание, что побитовое И или побитовое ИЛИ одного элемента равно самому этому элементу.

Ваша цель — сделать строку $$$s$$$ отсортированной в неубывающем порядке$$$^{\text{†}}$$$.

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

$$$^{\text{∗}}$$$Двоичная строка содержит только символы $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Если строка $$$s$$$ отсортирована в неубывающем порядке, то $$$s_1 \leq s_2 \leq \ldots \leq s_n$$$.

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

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

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

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

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

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

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

Пример
Входные данные
6
4
0011
4
1000
5
01000
8
01001101
7
0101010
7
0111101
Выходные данные
0
3
1
2
3
1
Примечание

В первом наборе входных данных строка уже отсортирована, поэтому операции не требуются.

Во втором наборе входных данных мы можем использовать побитовое OR, чтобы изменить последние три символа на 1, получив 1111 за $$$3$$$ операции.