For a string $S$, let $c_S(T)$ denote the number of occurrences of $T$ in $S$. For all palindromic strings $T$, find $\max_T(c_S(T) \cdot |T|^2)$.

Input

The input consists of a single line containing a string $S$, which consists only of lowercase English letters.

Output

Output a single integer representing the answer.

Examples

Input 1

hyddakioizjoi

Output 1

9

Note

Take $T=\mathsf{ioi}$.

Input 2

hyakioivilavpnshadowsocksapioioihyakioiagain

Output 2

36

Note

Take $T=\mathsf{ioi}$.