Palíndromo

Uma cadeia de caracteres é chamada de palíndromo se a sequência de caracteres da esquerda para a direita é igual à sequência de caracteres da direita para a esquerda (uma outra definição é que o primeiro caractere da cadeia deve ser igual ao último caractere da cadeia, o segundo caractere deve ser igual ao penúltimo caractere, o terceiro caractere deve ser igual ao antepenúltimo caractere, e assim por diante).

Por exemplo, as cadeias de caracteres “mim”, “axxa” e “ananaganana” são exemplos de palíndromos. Se uma cadeia não é palíndroma, ela pode ser dividida em cadeias menores que são palíndromas. Por exemplo, a cadeia “aaxyx” pode ser dividida de quatro maneiras distintas, todas elas contendo apenas cadeias palíndromas: {“aa”, “xyx”}, {“aa”, “x”, “y”, “x”}, {“a”, “a”, “xyx”} e {“a”, “a”, “x”, “y”, “x”}.

Dada uma cadeia de caracteres, escreva um programa que determine qual o menor número de partes em que a dada cadeia deve ser dividida de forma que todas as partes sejam palíndromos.

Entrada

A primeira linha contém um número inteiro $N$ que indica o número de caracteres da cadeia. A segunda linha contém a cadeia de caracteres, composta por letras minúsculas, de ‘a’ a ‘z’, sem espaços em branco.

Saída

Seu programa deve produzir uma única linha, contendo um número inteiro, o menor número de partes em que a cadeia de entrada deve ser dividida de forma que todas as partes sejam palíndromas.

Restrições

• $1 \leq N \leq 2\ 000$
• A cadeia de caracteres contém apenas letras minúsculas não acentuadas (‘a’ a ‘z’).

Informações sobre a pontuação

• Em um conjunto de casos de teste somando $20$ pontos, $N \leq 8$
• Em um conjunto de casos de teste somando $40$ pontos, $N \leq 300$

Exemplos

Exemplo de entrada 1

3
axa

Exemplo de saída 1

1

Exemplo de entrada 2

6
xyzyyx

Exemplo de saída 2

4

Exemplo de entrada 3

10
bbabcbbaab

Exemplo de saída 3

4