E. Большинство побеждает?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная строка$$$^{\text{∗}}$$$ $$$s$$$ длины $$$n$$$.

За одну операцию с бинарной строкой $$$g$$$ длины $$$k$$$ можно сделать следующее:

  • выбрать некоторые $$$l, r$$$, такие, что $$$1 \leq l \leq r \leq k$$$;

  • заменить подстроку$$$^{\text{†}}$$$ $$$g_l, \ldots, g_r$$$ строки $$$g$$$ на один символ, который встречается в этой подстроке не меньше, чем другой символ.

Стоимость такой операции будет равна $$$r-l+1$$$.

Например, строку 010010 за одну операцию стоимостью $$$4$$$ можно перевести в 010, заменив подстроку 1001 на 1; строку 1111 можно перевести в 1, сделав операцию стоимостью $$$4$$$ со всей строкой, а строку 0100 можно перевести, например, в 00, взяв в качестве подстроки 100.

Вам требуется найти минимальную стоимость того, чтобы перевести всю строку $$$s$$$ в строку 1, используя несколько (возможно, ни одной) операций, или определить, что это невозможно.

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

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

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

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

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

Вторая строка каждого описания набора входных данных содержит строку длины $$$n$$$, состоящую из символов 0 и 1 — строка $$$s$$$.

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

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

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

Пример
Входные данные
7
1
0
1
1
2
00
2
10
3
010
8
00111000
6
100100
Выходные данные
-1
0
-1
2
4
9
7
Примечание

В первом наборе входных данных невозможно получить 1, ведь единственная возможная операция ($$$l = r = 1$$$) не меняет строку.

Во втором наборе входных данных изначально строка уже равна 1, поэтому ответ 0.

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