Maximum LCP of Reversed LCS and LCP in a String

Given a string (S) of length (n), consider the following functions defined on (S):

• (\text{Rev}(S)): the string obtained by reversing (S), i.e., (S_{|S|}S_{|S|-1}\dots S_1).
• (\text{lcp}(i,j)): the longest common prefix (as a string) of the suffixes of (S) starting at positions (i) and (j) respectively.
• (\text{lcs}(i,j)): the longest common suffix (as a string) of the prefixes of (S) ending at positions (i) and (j) respectively.
• (\text{LCP}(S,T)): the longest common prefix of strings (S) and (T).

For every pair (1 \le i < j \le n), define a value

[ F(i,j)=\text{LCP}(\text{Rev}(\text{lcs}(i,j)),\text{lcp}(i,j)) ]

Here, if (\text{lcs}(i,j)=S[i-\ell+1\ldots i]) and (\text{lcp}(i,j)=S[i\ldots i+a-1]), then (\text{Rev}(\text{lcs}(i,j))) becomes (S[i]S[i-1]\dots S[i-\ell+1]). Thus, (F(i,j)) equals the maximum integer (r) such that (r\le a,,r\le\ell) and for every (0\le t<r) it holds that (S[i-t]=S[i+t]).

Your task is to compute the maximum such value over all valid pairs ((i,j)). In other words, output the maximum length of the common prefix between (\text{Rev}(\text{lcs}(i,j))) and (\text{lcp}(i,j)).

inputFormat

A single line containing the string (S).

outputFormat

Output a single integer denoting the maximum value of (F(i,j)) over all pairs (1 \le i < j \le n).

sample

abba

1