SPOJ Brasil

Gene e Gina possuem um tipo peculiar de fazenda. Ao invés de criar animais e plantar vegetais como acontece em fazendas normais, eles cultivam strings. Uma string é uma sequência de caracteres. As strings, ao crescerem, adicionam caracteres à esquerda e/ou à direita delas mesmas, mas nunca perdem caracteres nem inserem caracteres no meio.

Gene e Gina possuem uma coleção de fotos de algumas strings durante diferentes etapas de seus crescimentos. O problema é que a coleção não é rotulada, portanto eles esqueceram a qual string pertence cada uma das fotos. Eles querem montar um painel para ilustrar os procedimentos do cultivo de strings, mas eles necessitam sua ajuda para encontrar uma sequência de fotos apropriada.

Cada foto ilustra uma string. A sequência de fotos precisa ter a seguinte propriedade: se s_i aparece imediatamente antes de s_i+1 na sequência, então s_i+1 é uma string que pode ter crescido a partir de s_i (ou seja, s_i é uma substring contígua de s_i+1). Além disso, eles não querem usar fotos repetidas, portanto todas as strings na sequência devem ser diferentes.

Dado um conjunto de strings representando todas as fotos disponíveis, sua tarefa é calcular o tamanho da maior sequência que pode ser produzida com as restrições acima.

Entrada

Cada caso de teste se estende por várias linhas. A primeira linha contém um inteiro N representando o número de strings no conjunto (1 ≤ N ≤ 10⁴). Cada uma das próximas N linhas contém uma string não-vazia e única com no máximo 1000 caracteres minúsculos do alfabeto inglês. Em cada caso de teste, a soma dos tamanhos das strings é no máximo 10⁶.

O último caso de teste é seguido de uma linha contendo um zero.

Saída

Para cada caso de teste, imprima uma única linha com um único inteiro representando o tamanho da maior sequência de fotos que pode ser produzida.

Exemplo

Entrada:
6
plant
ant
cant
decant
deca
an
2
supercalifragilisticexpialidocious
rag
0

Saída:
4
2