A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.
As an example, by inserting 2 characters, the string
Ab3bd can be transformed into a palindrome (
Adb3bdA). However, inserting fewer than 2 characters does not produce a palindrome.
The first line contains one integer: the length of the input string ~N~, ~3 \le N \le 5\,000~. The second line contains one string with length ~N~. The string is formed from uppercase letters from
Z, lowercase letters from
z and digits from
9. Uppercase and lowercase letters are to be considered distinct.
The first line contains one integer, which is the desired minimal number.