SPOJ Brasil

O sistema operacional do seu computador indexa os arquivos do seu disco rígido baseado no seu conteúdo, e provê busca textual sobre eles. O conteúdo de cada arquivo é uma cadeia não-vazia de caracteres minúsculos. Para realizar uma pesquisa, você especifica uma chave, que é também uma cadeia não-vazia de letras minúsculas. O resultado é uma lista de todos os arquivos que contém a chave como uma subcadeia. Uma cadeia s é uma subcadeia de uma cadeia t se t contém todos os caracteres de s como uma sequência contígua. Por exemplo, "foofoo", "cafoo", "foota" e "foo" todas contém "foo" como uma subcadeia, enquanto "foa", "fofo", "fioo" e "oofo" não contém.

Você sabe o conteúdo de cada arquivo no seu disco rígido, e gostaria de saber se cada subconjunto dos arquivos é pesquisável. Um subconjunto dos arquivos é pesquisável se existe pelo menos uma chave que produz exatamente a lista desses arquivos como resultado. Dado os conteúdos dos arquivos on seu disco rígido, você deve computar o número de subconjuntos não-vazios pesquisáveis.

Entrada

Cada caso de teste é descrito usando várias linhas. A primeira linha contém um inteiro F representando o número de arquivos do seu disco rígido (1 ≤ F ≤ 60). Cada uma das F linhas sequintes indica o conteúdo de um dos arquivos. O conteúdo de um arquivo é uma cadeia não-vazia de no máximo 104 caracteres; cada caracteres é uma das 26 letras minúsculas (de 'a' até 'z').

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

Saída

Para cada caso de teste imprima uma linha com um inteiro representando o número de conjuntos não-vazios pesquisáveis.

Exemplo

Entrada

6 
form 
formal 
malformed 
for 
man 
remake 
3 
cool 
cool 
old 
0 

Saída

11
3