Ключ к шифру

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

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

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

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