题目描述

给定一个由英文字母和数字组成的字符串。你可以在字符串中的任意位置插入字符，请求出至少插入多少个字符，才能使整个字符串变成回文串。

例如，Ab3bd 可以插入两个字符变为 dAb3bAd，因此答案为 $2$。

输入格式

第一行输入一个整数 $N$，表示字符串长度。

第二行输入字符串。

输出格式

输出一个整数，表示最少需要插入的字符数。

数据范围与约定

$3\le N\le5000$；字符串只含大小写英文字母和数字。

可见测试数据

输入数据 1

5
Ab3bd

输出数据 1

2

输入数据 2

8
XWYcxxcX

输出数据 2

2

输入数据 3

16
g7tvi2dp6006pd7g

输出数据 3

4