Problem Description

Xiaoming especially likes palindromic strings, but palindromic strings are rare. So he defines two non-overlapping prefix and suffix of the same length of a string as a “palindromic prefix-suffix” if and only if concatenating this prefix and suffix forms a palindrome. Then, for a string $S=c_1c_2c_3,\cdots,c_n$, the length $L(S)$ of the “longest palindromic prefix-suffix” is

where $S_{[i,j]}$ denotes a substring $c_ic_{i+1}\cdots c_j$ of $S$, and $S^T$ denotes the string obtained by reversing $S$.

For a given string $S$, Xiaoming wants to modify it so that $L(S^\prime)$ is as large as possible. The modification allows deleting any substring of arbitrary length from the string. For example, after deleting the substring $S_{[3,5]}$ from $S = \texttt{abcdebijbba}$, $S$ becomes $\texttt{abbijbba}$.

Xiaoming wants to know: after the modification, what is the maximum possible value of $L(S^\prime)$ for the new string $S^\prime$?

Input Format

The input consists of $1$ line, a string $S$.

Output Format

The output consists of $1$ line, an integer representing the answer.

abcdebijbba

3

Hint

Sample Explanation

In the approach described in the statement, after deleting $S_{[3,5]}$, $S^\prime = \texttt{abbijbba}$, and $L(S^\prime) = 3$.

Constraints

For $20\%$ of the testdata, $|S| \le 500$.
For $100\%$ of the testdata, $|S| \le 500000$, and $S$ contains only lowercase letters.

Translated by ChatGPT 5