题目描述

给定一个长度为 $n$ 的由小写拉丁字母组成的字符串 $s$。

你可以对这个字符串应用一些操作：在一次操作中，你可以删除这个字符串的一些连续子串，但前提是你删除的子串中的所有字母都相同。

例如，从字符串 abbbbaccdd 中删除子串 bbbb 后，我们得到字符串 aaccdd。

计算删除整个字符串 $s$（即将字符串 $s$ 变成空串）所需的最小操作次数。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 500$），表示字符串 $s$ 的长度。

第二行包含由小写拉丁字母组成的字符串 $s$（$|s| = n$）。

输出格式

输出一个整数，表示删除字符串$s$所需的最小操作次数。

样例

5
abaca

3

8
abcddcba

4