E. Длинное инвертирование
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана бинарная строка $$$s$$$ из $$$n$$$ символов. Бинарной строкой называется строка, состоящая только из символов '1' и '0'.

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

С помощью операций нужно сделать все символы в строке равными '1'.

Например, если $$$n=5$$$, $$$s=00100$$$, то можно выбрать $$$k=3$$$ и действовать следующим образом:

  • выбрать отрезок от $$$1$$$-го до $$$3$$$-го символа и получить $$$s=\color{blue}{110}00$$$;
  • выбрать отрезок от $$$3$$$-го до $$$5$$$-го символа и получить $$$s=11\color{blue}{111}$$$;

Найдите максимальное значение $$$k$$$, при котором можно с помощью операций сделать все символы строки равными '1'. Обратите внимание, что количество операций, которые для этого нужно совершить, не имеет значения.

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — длину строки $$$s$$$.

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

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

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

Для каждого набора входных данных выведите максимальное целое число $$$k$$$ ($$$1 \le k \le n$$$), при котором возможно с помощью описанных операций получить строку $$$s$$$, состоящую только из символов '1'.

Пример
Входные данные
5
5
00100
5
01000
7
1011101
3
000
2
10
Выходные данные
3
2
4
3
1