For a string $S$, let $c_S(T)$ denote the number of occurrences of $T$ in $S$. Find $\max_T([c_S(T) \ne 0] \cdot |T|)$ for all palindromic strings $T$.

Input

The input consists of a single line containing a string $S$.

Output

Output a single integer representing the answer.

Subtasks

For all test cases, $|S| \leq 10^6$.

• Subtask 1 (35 Points): $|S| \leq 3.5 \times 10^4$.
• Subtask 2 (65 Points): No additional constraints.

Examples

Input 1

hyddakioizjoi

Output 1

3

Note 1

Take $T=\mathsf{ioi}$.

Input 2

hyakioivilavpnshadowsocksapioioihyakioiagain

Output 2

5

Note 2

Take $T=\mathsf{ioioi}$.