题目描述

给定一个长度不超过 n 的字符串 s，如果 s 中的一个子序列是回文，那么我们就可以从 s 中移除这个子序列，求最少经过多少步我们可以移除整个字符串 s。如：我们可以从"dqewfretd"中移除 "defed"，剩下的字符串即："qwrt"。

输入格式

第1行包含1个整数 $n (1\le n \le18)$ 。

第2行包含n个字符的字符串 $s$ 。

输出格式

输出一个整数,表示最小步数。

样例输入 #1

9
dqewfretd

样例输出 #1

5

样例输入 #2

6
abctab

样例输出 #2

2