Marina loves palindromes very much. Palindrome — is a string that reads the same from left to right and from right to left, such as « noon "," rotator » or " radar».
Marina wrote a string s on the board, consisting of n lowercase Latin letters s
1 s
2 ... s
n . A substring of the string s is the string s
ls l + 1 ... s
r for some 1 ≤ l≤ r ≤ n. Marina searches the string s for the longest possible substring that is a palindrome. For example, in the line " rotateradar » such a substring would be « radar».
Vova wants to change the line written by Marina so that the palindrome substring is as long as possible. He can either leave the string intact, or change exactly one letter in it to another. For example, if the line " rotateradar » change the sixth letter to " o », you get the string « rotatoradars », in which the maximum palindrome substring « rotator » has length 7 . A palindrome substring of greater length cannot be obtained.
Help Vova determine the maximum length of a palindrome substring he can get.
Input
The first line of the input contains a natural number n — the length of the string Marina wrote ( 1 ≤ n ≤ 100 ).
The second line of the input contains the string itself, consisting of n lowercase Latin letters.
Imprint
In the output file print a single number — the maximum length of a palindrome substring that Vova can get.
Examples
| # |
Input |
Output |
| 1 |
12
rotateradar |
7 |