Ты думал, что тут будет легенда про ДжоДжо? Но нет, это был я, Дио!
Дана бинарная строка \(s\) длины \(n\), состоящая из символов 0 и 1. Построим квадратную таблицу размера \(n \times n\), состоящую из символов 0 и 1 следующим образом.
В первую строку таблицы запишем исходную строку \(s\). Во вторую строку таблицы запишем циклический сдвиг строки \(s\) на один вправо. В третью строку таблицы запишем циклический сдвиг строки \(s\) на два вправо. И так далее. Таким образом, в строке с номером \(k\) будет записан циклический сдвиг строки \(s\) на \(k\) вправо. Строки таблицы пронумерованы от \(0\) до \(n - 1\) сверху вниз.
В получившейся таблице требуется найти прямоугольник, состоящий только из единиц, имеющий наибольшую площадь.
Прямоугольником мы называем множество всех клеток таблицы \((i, j)\) таких, что \(x_1 \le i \le x_2\) и \(y_1 \le j \le y_2\) для некоторых целых чисел \(0 \le x_1 \le x_2 < n\) и \(0 \le y_1 \le y_2 < n\).
Напомним, что циклическим сдвигом строки \(s\) на \(k\) вправо называется строка \(s_{n-k+1} \ldots s_n s_1 s_2 \ldots s_{n-k}\). Например, циклическим сдвигом строки «01011» на \(0\) вправо является сама строка «01011», её циклическим сдвигом на \(3\) вправо является строка «01101».
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную площадь прямоугольника, состоящего только из единиц. Если такого прямоугольника не существует, выведите \(0\).
Примечание
В первом наборе входных данных получается таблица \(1 \times 1\), состоящая из единственного символа 0, таким образом нет прямоугольников, состоящих из единиц, и ответ \(0\).
Во втором наборе входных данных получается таблица \(1 \times 1\), состоящая из единственного символа 1, поэтому ответ равен \(1\).
В третьем наборе входных данных получается таблица:
В четвёртом наборе входных данных получается таблица:
| 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
В пятом наборе входных данных получается таблица:
| 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
Прямоугольники с максимальной площадью выделены жирным шрифтом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
0
1
101
011110
101010
|
0
1
2
6
1
|