Description

众所周知，小图精通字符串。

一天，小图意外的获得了一个字符串，但他发现这个字符串并不是一个回文串，因此他非常生气。于是他决定从这个字符串中删除若干个字符使得剩余的字符串为一个回文串。

回想回文串的定义：如果一个字符串正着读和反着读都是一样的字符串，那么这个字符串就是回文串。

Format

Input

第一行有一个正整数 $n(1 \le n \le 2000)$，表示字符串的长度。

第二行有一个长度为 $n$ 仅含有小写字母的字符串 $s$。

Output

输出一个整数，表示使得剩余字符串为回文串最少删除的字符数量。

Samples

6
aabcaa

1

10
asdbdbdadb

3

样例1解释

删除字符 b 或 c，可以使得剩下得字符串为回文串。