给定一个字符串 $$$s$$$,长度为 $$$n$$$,由小写拉丁字母组成。您可以对该字符串应用一些操作:如果您删除的子字符串中的所有字母都相等,则在一次操作中您可以删除该字符串的某些连续子字符串。例如,从字符串 abbbbaccdd 中删除子字符串 bbbb 后,我们得到字符串 aaccdd。
计算删除整个字符串$$$s$$$的最少操作次数。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 字符串 $$$s$$$ 的长度。
第二行包含由小写拉丁字母组成的字符串 $$$s$$$ ($$$|s| = n$$$)。
输出
输出单个整数 — 删除字符串 $$$s$$$ 的最少操作次数。
示例
输入 #1
5 abaca
输出 #1
3
输入 #2
8 abcddcba
输出 #2
4