Будем говорить, что строка s является повтором длины k, если существует такая строка t, что s = t * k, где под умножением подразумевается конкатенация k экземпляров строки t один за другим.

Например, строка abababab является повтором строки abab длины 2, а также повторением строки ab длины 4. Тогда имеет смысл говорить о наибольшем повторе. Строка является наибольшим повтором длины k, если она является повтором некоторой строки длины k и если не существует такой строки t, что s —– повтор t длины m > k. Например, строка aaaa является наибольшим повтором длины 4.

Вам дана строка, которая является наибольшим повтором длины x. Найдите x.
Заметим, что ответ всегда равен хотя бы единице, так как строка является повтором самой себя.

В единственной строке дана строка, состоящая из строчных букв английского алфавита и не превышающая в длину 10⁶. Строка не бывает пустой.

Выведите единственное число — x, длину наибольшего повтора.