该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

给一个数组，每次可以删除一段连续相同的子串。最少删几次清空数组？

题目描述

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

你可以对该字符串进行若干次操作：在一次操作中，你可以删除该字符串中的某个连续且相同的子串。

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

计算删除整个字符串 $s$ 所需的最少操作次数。

输入格式

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

第二行输入由小写字母组成的字符串 $s$ ( $|s| = n$ )。

输出格式

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

输入输出样例 #1

输入 #1

5
abaca

输出 #1

3

输入输出样例 #2

输入 #2

8
abcddcba

输出 #2

4