Cipher Key

Hercule Poirot is currently exposing an international criminal syndicate that smuggles works of art. Police working with Poirot intercepted an encrypted letter with the place and time of an upcoming deal, which the head of the syndicate will attend. To stop the deal and arrest the head, the intercepted letter must be decrypted.

Hercule knows that the key to the cipher is computed from a string $s$. For a string $w$, let $f(w)$ be the length of the longest suffix of $w$ that is not equal to $w$ and is also a prefix of $w$. For example, $f(`abc`) = 0$, $f(`abab`) = 2$, $f(`aaa`) = 2$. The key is the maximum of $|t| + f(t)^2$ over all substrings $t$ of $s$. Help Hercule compute the key.

The only line contains the string $s$, consisting of lowercase Latin letters ($1 \le |s| \le 500000$).

Print a single integer, the key to the cipher.