Дана бинарная строка $$$s$$$ из $$$n$$$ символов. Бинарной строкой называется строка, состоящая только из символов '1' и '0'.
Вы можете выбрать целое число $$$k$$$ ($$$1 \le k \le n$$$), после чего применить любое число раз следующую операцию: выбрать $$$k$$$ подряд идущих символов строки и инвертировать их, то есть заменить все '0' на '1' и наоборот.
С помощью операций нужно сделать все символы в строке равными '1'.
Например, если $$$n=5$$$, $$$s=00100$$$, то можно выбрать $$$k=3$$$ и действовать следующим образом:
Найдите максимальное значение $$$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'.
5500100501000710111013000210
3 2 4 3 1
| Codeforces Round 938 (Div. 3) |
|---|
| Закончено |
