关于制造回文

描述

回文，亦称回环，是正读反读都能读通的句子，亦有将文字排列成圆圈者，是一种修辞方式和文字游戏。回文运用得当，可以表現两种事物或现象相互依靠或排斥的关系。总有人以为回文是英文的专利，其实不然，中文中也有很多回文的例子，譬如：



莺啼岸柳弄春晴， 柳弄春晴夜月明。

明月夜晴春弄柳， 晴春弄柳岸啼莺。



看着很有意思，可要想写出回文，并不是一件很容易的事情。如果有一个字符串，怎样才能插入最少的内容，把它变成回文呢？



例如，要想把字符串 "Zb3bd" 变成回文，就需要插入两个字符，变成 "dZb3bZd" 或者 "Zdb3bdZ"，插入一个字符，是肯定不行的。



输入

输入的第一行是字符串的长度 N，3 <= N <= 5000，第二行是一个长度为 N 的字符串。该字符串由英文大小写字母和数字组成，英文大写字母和小写字母是不同的。



输出

程序输出要把该字符串变成回文，需要插入的最少字符数。-On the manufacture of palindrome