Maximizing Palindromic Prefix-Suffix

Given a string \(S = c_1 c_2\cdots c_n\), define its palindromic prefix-suffix of length \(x\) as follows: Let the first \(x\) characters \(S_{[1,x]}\) and the last \(x\) characters \(S_{[n-x+1,n]}\) be non overlapping parts of \(S\). They form a palindromic prefix-suffix if and only if

[ S_{[1,x]} = \bigl(S_{[n-x+1,n]}\bigr)^T, ]

where \(S^T\) denotes the reversal of string \(S\). Denote by \(L(S)\) the maximum \(x\) (possibly zero) for which the above holds. Note that if no such nonnegative integer exists (other than \(0\)), then \(L(S)=0\).

You are allowed to transform \(S\) by deleting one arbitrary contiguous substring (the deleted substring may be of any length, possibly zero) to obtain a new string \(S'\). For example, deleting the substring \(S_{[3,5]}\) from abcdebijbba results in abbijbba.

Your task is to maximize \(L(S')\) over all possible deletions and output the maximum value.

inputFormat

The input consists of a single line containing the string \(S\), consisting of only ASCII characters.

\(1 \leq |S| \leq 5000\) (for example).

outputFormat

Output a single integer representing the maximum possible value of \(L(S')\) after performing at most one deletion of a contiguous substring.

sample

abcdebijbba

3