Ключ к шифру
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сейчас Эркюль Пуаро занят разоблачением международного преступного синдиката, занимающегося контрабандой предметов искусства. Полиция, сотрудничающая с Пуаро, перехватила зашифрованное письмо, содержащее информацию о месте и времени предстоящей сделки, на которой будет присутствовать и глава синдиката. Для того, чтобы чтобы сорвать сделку и задержать главу синдиката, необходимо расшифровать перехваченное письмо.

Эркюль знает, что ключ к шифру вычисляется из строки s. Обозначим за f(w) длину максимального суффикса w, не равного w, который является и префиксом w. Например, , , . Тогда, ключом является максимум по всем t, являющимися подстроками s, (|t| + f(t)2). Помогите Эркюлю вычислить ключ.

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

В единственной строке дана строка s, состоящая из строчный латинских букв (1 ≤ |s| ≤ 500 000).

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

Выведите единственное целое число — искомый ключ к шифру.

Пример

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