SPOJ Brasil

Uma área extensiva de pesquisa na ciência da computação é o campo da comunicação. Com redes de computadores fazendo parte da vida cotidiana de muitas pessoas, a criação de maneiras para torná-las mais rápidas, confiáveis e seguras é necessária com freqüência. Essa necessidade prática motiva uma atividade de pesquisa extensiva na teoria por trás das comunicações.

A primeira coisa necessária para estabelecer qualquer tipo de comunicação é um código comum. Um código é um jeito de mudar a forma de um pedaço de informação em alguma outra forma, em geral para tornar possível o transporte de informação de um lugar para o outro. Códigos de bandeiras usados por barcos e o código Morse usado na telegrafia são exemplos de códigos para traduzir letras em diferentes formatos e permitir a comunicação através de diferentes meios.

Mais formalmente, um código é um conjunto de strings composto de símbolos de um alfabeto. Cada string definida no código é chamada uma palavra código. Uma mensagem é então composta concatenando uma série de palavras código para transmitir a informação necessária. Por exemplo, em código Morse o alfabeto é composto dos símbolos hífen e ponto; a letra “S” é representada pela palavra código “...”, a letra “0” é representada pela palavra código “---”, e portanto a mensagem de emergência “SOS” em código morse é “...---...”.

Códigos para comunicação podem ter muitas propriedades desejadas e indesejadas, como ambigüidade, entropia, redundância, e muitas outras. Nessa problema nós focaremos na ambigüidade como uma propriedade chave.

Um código é ambíguo quande existe uma mensagem usando aquele código que pode ser particionada em diferentes seqüências de palavras código. Em outras palavras, em um código ambíguo a mensagem pode ter mais de um significado. Por exemplo, considete o alfabeto binário composto de símbolos {0, 1}. Para o código composto das palavras {10, 01, 101} a mensagem 10101 pode ser entendido como 10-101 ou 101-01 e portanto o código é ambíguo. Por outro lado, para o código composto das palavras {01, 10, 011} não nenhuma mensagem ambígua e portanto o código é não-ambíguo.

Como parte de uma comunidade de ciência da computação, você é pedido para desenvolver um testador que verifica se códigos são ambíguos. No caso de um código ser realmente ambíguo, você também é requisitado a falar o comprimento (i.e. o número de símbolos) da mensagem ambígua mais curta para aquele código.

Entrada

Cada caso de teste consistirá de várias linhas. Em todos casos de teste o alfabeto será o conjunto de dígitos hexadecimais (dígitos decimais mais as letras maiúsculas “A” até “F”). A primeira linha de um caso de teste terá um inteiro N (1 <= N <= 100), o número de palavras código no código. Cada uma das próximas N linhas descreve uma palavra código e contém uma string diferente e não-vazia de até 50 dígitos hexadecimais. A entrada é terminada por N = 0.

Saída

Para cada caso de teste, imprima uma única linha com o comprimento da mensagem ambígua mais curta para o código fornecido ou -1 se o código não é ambíguo.

Exemplo

Entrada
3
10
01
101
3
AB
BA
ABB
0

Saída
5
-1