题目描述

回文字符串指的是对称字符串，也就是该字符串从左到右读和从右到左读得到的结果是一样的。

给定任意的一个字符串，如果该字符串不是回文字符串，通过插入若干字符，可以将该字符串改造为回文字符串。

给定一个字符串，请问该字符串最少插入多少个字符，可以使得该字符串成为回文字符串？

比如：字符串"ab3bd"，在插入2个字符后可以变成一个回文词："dab3bad"或"adb3bda"。然而插入2个以下的字符，无法使其变成一个回文字符串。

输入

第一行为一个整数 $n$ （ $3≤n≤5000$ ），表示给定字符串的长度。

第二行为长度为 $n$ 的不含空格的字符串。

输出

一个数，要插入的最少字符数。

样例

5
ab3bd

2