F. Я могу ошибаться
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

  • Выберите два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$). Пусть $$$cnt_0$$$ это количество вхождений 0 в $$$S[l \ldots r]$$$, а $$$cnt_1$$$ это количество вхождений 1 в $$$S[l \ldots r]$$$. Вы можете заплатить $$$|cnt_0 - cnt_1| + 1$$$ монет и отсортировать $$$S[l \ldots r]$$$. (Как $$$S[l \ldots r]$$$ мы обозначаем подстроку $$$S$$$, начинающуюся в позиции $$$l$$$ и заканчивающуюся в позиции $$$r$$$).

    Например, если $$$S = $$$ 11001, мы можем выполнить операцию над $$$S[2 \ldots 4]$$$ за $$$|2 - 1| + 1 = 2$$$ монеты и получить $$$S = $$$ 10011 в качестве новой строки.

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

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

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

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

Вторая строка каждого набора входных данных содержит бинарную строку $$$S$$$ из $$$n$$$ символов $$$S_1S_2 \ldots S_n$$$. ($$$S_i = $$$ 0 или $$$S_i = $$$ 1 для каждого $$$1 \le i \le n$$$).

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

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

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

Пример
Входные данные
7
1
1
2
10
3
101
4
1000
5
11010
6
110000
20
01000010001010011000
Выходные данные
0
1
1
3
2
2
5
Примечание

В первом наборе входных данных $$$S$$$ уже отсортирована.

Во втором наборе входных данных достаточно применить операцию с $$$l = 1, r = 2$$$.

В третьем наборе входных данных достаточно применить операцию с $$$l = 1, r = 2$$$.