Hacked String

Lew sends Chris a string and asks for its longest palindromic substring. During the process, someone hacked the file and changed one character.

Chris wonders, what could be the length of the longest palindromic substring in the initial string?

Here is the string after the modification.

Sample Input

dabcaaef

Sample Output

5

Explanation

If we change the fifth character to b then the longest palindromic substring is abcba . There will be no palindromic substring longer than this after any modification of one character.

Details and Assumptions

• The length of the string is 1000.
• The file only contains lowercase alphabetical letter.