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

Вам дана бинарная строка $$$s$$$ длиной $$$n$$$ и печатный станок с двумя кнопками: 0 и 1. Изначально ваш палец находится на кнопке 0. Вы можете выполнять следующие две операции:

  1. Нажать на кнопку, на которой в данный момент находится ваш палец. Это напечатает символ, который находится на кнопке.
  2. Переместить палец на другую кнопку. Если ваш палец находится на кнопке 0, переместите его на кнопку 1, и наоборот.

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

Перед печатью вы можете развернуть не более одной подстроки$$$^{\text{∗}}$$$ строки $$$s$$$. Более формально, вы можете выбрать два индекса $$$1\le l\le r\le n$$$ и развернуть подстроку $$$s_{l\ldots r}$$$, в результате чего получится новая строка $$$s_1s_2\ldots s_{l-1}s_rs_{r-1}\ldots s_ls_{r+1}\ldots s_n$$$.

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

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

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

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

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

Вторая строка каждого набора входных данных содержит бинарную строку $$$s_1s_2\ldots s_n$$$ ($$$s_i = \mathtt{0}$$$ или $$$s_i = \mathtt{1}$$$) — символы бинарной строки $$$s$$$.

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

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

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

Пример
Входные данные
6
3
000
3
111
3
011
3
100
5
10101
19
1101010010011011100
Выходные данные
3
4
4
4
8
29
Примечание

В первом наборе входных данных мы можем не разворачивать никакие подстроки. Мы можем выполнить операцию $$$1$$$ три раза, чтобы напечатать 000.

Во втором наборе входных данных мы можем не разворачивать никакие подстроки. Мы можем выполнить операцию $$$2$$$, чтобы переместить палец на кнопку 1. Затем мы выполняем операцию $$$1$$$ три раза, чтобы напечатать 111.

В третьем наборе входных данных мы можем не разворачивать никакую подстроку. Мы можем выполнить операцию $$$1$$$, чтобы напечатать 0. Затем мы выполняем операцию $$$2$$$, чтобы переместить палец на кнопку 1. Наконец, мы выполняем операцию $$$1$$$ два раза, чтобы напечатать 11, в результате чего получаем финальную строку 011, используя всего $$$4$$$ операции.

В четвертом наборе входных данных мы можем развернуть подстроку $$$s_{1\ldots 3}$$$, в результате чего получится строка 001. Мы можем выполнить операцию $$$1$$$ два раза, чтобы напечатать 00. Далее мы выполняем операцию $$$2$$$, чтобы переместить палец на кнопку 1. Наконец, мы выполняем операцию $$$1$$$ один раз, чтобы напечатать 1, в результате чего получаем финальную строку 001, используя всего $$$4$$$ операции.

В пятом наборе входных данных мы можем развернуть подстроку $$$s_{2\ldots 3}$$$, в результате чего получится строка 11001. Стоимость строки составляет $$$8$$$, так как мы можем выполнить следующую последовательность операций:

  • Выполнить операцию $$$2$$$, чтобы переместить палец на кнопку 1.
  • Выполнить операцию $$$1$$$ два раза, чтобы напечатать 11.
  • Выполнить операцию $$$2$$$, чтобы переместить палец на кнопку 0.
  • Выполнить операцию $$$1$$$ два раза, чтобы напечатать 00.
  • Выполнить операцию $$$2$$$, чтобы переместить палец на кнопку 1.
  • Выполнить операцию $$$1$$$ один раз, чтобы напечатать 1.

В шестом наборе входных данных мы можем развернуть подстроку $$$s_{5\ldots 17}$$$, в результате чего получится строка 1101111011001001000. Можно доказать, что минимальное количество операций, необходимое для печати данной бинарной строки, составляет $$$29$$$.