Дана бинарная строка \(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'. Обратите внимание, что количество операций, которые для этого нужно совершить, не имеет значения.
Выходные данные
Для каждого набора входных данных выведите максимальное целое число \(k\) (\(1 \le k \le n\)), при котором возможно с помощью описанных операций получить строку \(s\), состоящую только из символов '1'.