题目描述

小明特别喜欢回文串，然而回文串太少见了，因此他定义了一个字符串的相同长度的、不相交的前缀和后缀是“回文前后缀”，当且仅当这个前缀和后缀拼起来是个回文串。那么字符串 $S=c_1c_2c_3,\cdots,c_n$ 的“最长回文前后缀” 的长度 $L(S)$ 即为 $\argmax\limits_{x}{S_{[1,x]} = (S_{[n-x+1,n]})^T}$ 其中 $S_{[i,j]}$ 表示 $S$ 的一个子串 $c_ic_{i+1}\cdots c_j$，$S^T$ 表示翻转 $S$ 得到的字符串。

对于一个给定的字符串 $S$，小明希望对其进行改造使得 $L(S ^\prime)$ 尽可能大。改造允许将字符串中一个任意长度的子串删除。比如删除 $S = \texttt{abcdebijbba}$ 中 的子串 $S_[3,5]$ 后 $S$ 变成了 $\texttt{abbijbba}$。

小明想知道改造后的新字符串 $S^\prime$ 的“最长回文前后缀”的长度 $L(S^\prime)$ 最大是多少？

输入格式

输入共 $1$ 行，一个字符串 $S$。

输出格式

输出共 $1$ 行，一个整数表示答案。

abcdebijbba

3

提示

【样例说明】

如题干中的方案删除 $S_{[3,5]}$ 后，$S^\prime = \texttt{abbijbba}$，$L(S^\prime) = 3$。

【评测用例规模与约定】 对于 $20\%$ 的评测用例，保证 $|S| \le 500$。
对于 $100\%$ 的评测用例，保证 $|S| \le 500000$，$S$ 仅包含小写字母。