小明特別喜歡回文串，然而回文串太少見了，因此他定義了一個字符串的相同長度的、不相交的前綴和后綴是 “回文前后綴”，當且僅當這個前綴和后綴拼起來是個回文串。那么字符串 S = c₁c₂c₃, . . . , c_n 的 “最長回文前后綴” 的長度L(S ) 即為 arg maxxS _[1,x] = (S _[n?x+1,n])T 其中 S _{[i, j]} 表示 S 的一個子串 c_ic_i+1 . . . c_j，S^T 表示翻轉(zhuǎn) S 得到的字符串。

對于一個給定的字符串 S，小明希望對其進行改造使得 L(S′) 盡可能大。改造允許將字符串中一個任意長度的子串刪除。比如刪除 S = abcdebi jbba 中的子串 S _[3,5] 后 S 變成了 abbi jbba。

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

輸入共 1 行，一個字符串 S。

輸出共 1 行，一個整數(shù)表示答案。

abcdebijbba

3

【樣例說明】

如題干中的方案刪除 S _[3,5] 后，S′ = abbi jbba，L(S′) = 3。

【評測用例規(guī)模與約定】

對于 20% 的評測用例，保證 |S | ≤ 500。

對于 100% 的評測用例，保證 |S | ≤ 500000，S 僅包含小寫字母。