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

Бинарной строкой называется строка, состоящая только из символов 0 и 1. Вам дана бинарная строка $$$s_1 s_2 \ldots s_n$$$. Нужно сделать эту строку неубывающей за наименьшее количество операций. Иными словами, каждый символ должен быть не меньше предыдущего. За одну операцию вы можете сделать следующее:

  • Выбрать произвольный индекс в строке $$$1 \leq i \leq n$$$;
  • Для всех $$$j \geq i$$$ поменять значение в $$$j$$$-й позиции на противоположное, то есть если $$$s_j = 1$$$, то сделать $$$s_j = 0$$$, и наоборот.

За какое минимальное количество операций можно сделать строку неубывающей?

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

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

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

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

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

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

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

Пример
Входные данные
8
1
1
2
10
3
101
4
1100
5
11001
6
100010
10
0000110000
7
0101010
Выходные данные
0
1
2
1
2
3
1
5
Примечание

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

Во втором наборе входных данных можно выбрать $$$i = 1$$$, и после этого $$$s = \mathtt{01}$$$.

В третьем наборе входных данных можно выбрать $$$i = 1$$$ и получить $$$s = \mathtt{010}$$$, а после этого выбрать $$$i = 2$$$. В результате получим $$$s = \mathtt{001}$$$, то есть неубывающую строку.

В шестом наборе входных данных можно на первой итерации выбрать $$$i = 5$$$ и получить $$$s = \mathtt{100001}$$$. Затем выбрать $$$i = 2$$$, тогда $$$s = \mathtt{111110}$$$. Дальше выбираем $$$i = 1$$$, и получаем неубывающую строку $$$s = \mathtt{000001}$$$.