SPOJ Brasil

Os juízes ICPC estão preparando um festa para a cerimônia de abertura. Para a festa, eles pretendem adicionar um playlist com algumas músicas para o software jukebox (um simples MP3 player). Entretanto, existem muitas músicas no computador, isso dificulta encontrar aquelas que eles querem adicionar. Como conseqüência, eles precisam usar algumas buscas muitas vezes.

Nesta jukebox, quando você pesquisa por uma string s, o software retorna todas músicas cujos títulos ou nomes de artistas contém s como uma substring. A string s é uma substring da string t se t contém todos os caracteres de s como uma seqüência contigua (por exemplo, 'bc' é uma substring de 'abcd', mas 'ac' não é). Para salvar o tempo precioso deles, enquanto procuram por uma música, eles sempre usam uma string de ouro da música, isto é, uma das mais curtas strings que retornam de uma pesquisa como resultado somente a música que eles querem.

Neste exemplo, uma possível string de ouro para a música 'johnnatan' é 'ta'. Note que 'ta' não é uma substring do nome de outra música nem é uma substring do nome do artista de outra música. Note também que não existem strings de tamanho igual a 1 que podem identificar unicamente a música 'johnnatan'.

Eles descobriram que se eles removem o campo artista de algumas músicas eles podem obter strings de ouro menores. Para a música 'john', não existe nenhuma string de ouro. Entretanto, se removermos o campo artista de todas as outras músicas, a string 'c' se torna a string de ouro para a música 'john'.

Dada uma lista de músicas (cada música com nome e artista), sua tarefa é determinar a soma mínima do tamanho das strings de ouro para todas as músicas que podem ser obtidas se em algumas removermos o campo artista. Na figura acima, você pode ver um possível melhor resultado com as strings de ouro em negrito. A soma mínima dos tamanhos das strings de ouro neste caso é 10.

Entrada

A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém um inteiro N (1<=N<=30), que indica o número de músicas. A seguir, existirão N pares de linhas (2*N linhas), um par para cada música. A primeira linha de um par contém o número da música, a linha conterá o nome da artista. Ambos, nome de artista e música, são strings contendo somente letras minúsculas e sobrescritos e terão no mínimo 1 e no máximo 30 caracteres. Existirão no máximo 6 artistas diferentes na lista. O fim da entrada é dado por N=0.

Saída

Para cada caso de teste seu programa deve produzir uma linha simples com a soma mínima dos tamanhos das strings de ouro. Você pode assumir que sempre existirá uma solução.

Exemplo de entrada 
8
a_flor
los_hermanos
anna_julia
los_hermanos
quem_sabe
los_hermanos
pierrot
los_hermanos
azedume
los_hermanos
johnny
massacration
johnnatan
massacration
john
massacration
4
c
axc
b
axc
d
cc
xc
cc
0

Exemplo de saída
10
5