Palindrome

Uma cadeia de caracteres é chamada de palíndrome se sequencia de caracteres da esquerda para a direita é igual à sequencia de caracteres da direita para a esquerda (uma outra definição é que o primeiro caractere da cadeia deve ser igual ao último caractere, o segundo caractere seja igual ao penúltimo caractere, o terceiro caractere seja igual ao antepenúltimo caractere, e assim por diante). Por exemplo, as cadeias de caracteres “mim”, “axxa” e “ananaganana” são exemplos de palíndromes.

Se uma cadeia não é palíndrome, ela pode ser dividida em cadeias menores que são palíndromes. Por exemplo, a cadeia “aaxyx” pode ser dividida de quatro maneiras distintas, todas elas contendo apenas cadeias palíndromes: {“aa”, “xyx”}, {“aa”, “x”, “y”, “x”}, {“a”, “a”, “xyx”} e {“a”, “a”, “x”, “y”, “x”}.

Escreva um programa que determine qual o menor número de partes em que uma cadeia deve ser dividida de forma que todas as partes sejam palíndromes. ## Entrada

A entrada é constituída de vários conjuntos de teste.

A primeira linha de um conjunto de testes contém um inteiro $N$ que indica o número de caracteres da cadeia ($1 \leq N \leq 2\ 000$). A segunda linha contém a cadeia de caracteres, composta por letras minúsculas (de ‘a’ a ‘z’), sem espaços em branco. O final da entrada é indicado por $N = 0$.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste $n$”, onde $n$ é numerado a partir de 1. A segunda linha deve conter um inteiro indicando o menor número de partes que a cadeia de entrada deve ser dividida de forma que todas as partes sejam palíndromes. A terceira linha deve ser deixada em branco.

Exemplo de Entrada 1

3
axa
6
xyzyyx
10
bbabcbbaab
0

Exemplo de Saída 1

Teste 1
1

Teste 2
4

Teste 3
4