You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

给你一个长度为 n 的只由小写字母组成的字符串 s。

每一次操作我们可以删除s的一段由同一个字母组成的连续子串。

例如：我们可以将abbbbaccdd删除bbbb得到aaccdd；但是不可以从abcde中删除bc。

问最少需要多少次操作能删除整个字符串s。

输入格式

第一行一个整数 n。

第二行一个只由小写字母组成的字符串s。

输出格式

一个整数，表示最少需要的操作数。

样例输入1

5
abaca

样例输出1

3

样例输入2

8
abcddcba

样例输出2

4

样例解释1：先删掉b剩下aaca；再删掉c，剩下aaa；最后删掉aaa。3次操作。

样例解释2：第1步删掉中间的dd，剩下abccba；第2步删掉中间的cc，剩下abba；第3步删掉bb，剩下aa；第4步删掉aa。且没有小于4次能删除的方法，故要4次操作。

评分方法

共25组数据，每组4分。

对于所有数据 $1 \le n \le 500$

其中5组数据，字符串s只由小写字母a,b组成

另有5组数据，$n \le 10$

另有8组数据，$n \le 60$