问题描述

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

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

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

输入格式

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

输出格式

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

abcdebijbba

3

样例说明

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

评测用例规模与约定

对于 $20\%$ 的评测用例，保证 $|S|≤500$。

对于 $100\%$ 的评测用例，保证 $|S|≤500000$，$S$ 仅包含小写字母。