Limpe a String

Você recebe uma string $s$ de tamanho $n$ composta apenas por letras minúsculas do alfabeto. Você pode aplicar algumas operações nessa string: Em uma operação você pode deletar alguma substring dessa string se, e somente se, todas as letras dessa substring são iguais. Por exemplo, depois de deletar a substring bbbb da string abbbbaccdd nós obtemos a string aaccdd.

Calcule o número mínimo de operações necessárias para deletar toda a string $s$.

Entrada

A primeira linha de entrada contém um inteiro $n$ $(1 \leq n \leq 500)$, onde $n$ é o tamanho da string $s$.

A segunda linha contém a string $s$ composta apenas por letras minúsculas do alfabeto.

Saída

Imprima apenas um inteiro: O número mínimo de operações para deletar a string $s$.

Exemplos

Entrada 1	Saída 1
5 abaca	3

Entrada 2	Saída 2
8 abcddcba	4