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