描述

回文（palindrome）是指对称的字符串，即从左到右和从右到左读取完全相同的字符串。你需要编写一个程序，给定一个字符串，计算最少需要插入多少个字符才能使其变为回文。

例如，字符串 "Ab3bd" 可以通过插入 2 个字符变成回文（如 "dAb3bAd" 或 "Adb3bdA"），但如果插入少于 2 个字符，则无法构成回文。

输入

你的程序需要从标准输入读取数据。

• 第一行包含一个整数 $N$，表示输入字符串的长度，满足 $3 \leq N \leq 5000$。
• 第二行包含一个长度为 $N$ 的字符串，仅由以下字符组成：
  • 大写字母 'A' 到 'Z'；
  • 小写字母 'a' 到 'z'；
  • 数字 '0' 到 '9'。
    注意： 大写和小写字母被视为不同的字符。

输出

你的程序需要向标准输出写入结果。

• 第一行包含一个整数，表示使字符串变为回文所需的最少插入字符数。

示例

输入数据 1：

5
Ab3bd

输出数据 1：

2

来源：
IOI 2000