提示: 欢迎访问OurACM平台。
Problem 1124 Palindrom

Accept: 98    Submit: 353
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem 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"). However, inserting fewer than 2 characters does not produce a palindrome.

Input

There are several test cases in the input. The first line of each test case contains one integer: the length of the input string N, (3<=N<=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'. Uppercase and lowercase letters are to be considered distinct.

A case with N=0 marks the end of input. This case should not be processed.

Output

For each test case, output one integer, which is the desired minimal number.

Sample Input

5 Ab3bd 0

Sample Output

2

Source

FZU 2004

Submit  Back  Status  Discuss