PKU/1159

回文 Time Limit: 3000MS 时间限制：3000MS Memory Limit: 65536K 内存限制：65536K Total Submissions: 26425 共提交：26425 Accepted: 8822 接受：8822

Description描述

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 ("dAb3bAd" or "Adb3bdA").作为一个例子，通过插入2个字符，字符串“Ab3bd”可以变成回文（“dAb3bAd”或“Adb3bdA”）。 However, inserting fewer than 2 characters does not produce a palindrome.然而，插入少于2个字符不会产生回文。

Input输入

Your program is to read from standard input.你的程序是从标准输入读取。 The first line contains one integer: the length of the input string N, 3 <= N <= 5000.第一行包含一个整数：在输入字符串的长度为N，3“= ñ”= 5000。 The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'.第二行包含一个字符串的长度N的字符串是由大写字母组成的'一'到'Z'和数字由'A'到'Z'，小写字母从0到9。 Uppercase and lowercase letters are to be considered distinct.大写和小写字母都被认为是不同的。 Output输出

Your program is to write to standard output.你的程序是写入到标准输出。 The first line contains one integer, which is the desired minimal number.第一行包含一个整数，这是所需的最小数量。 Sample Input样本输入

5
Ab3bd

Sample Output示例输出

2