Há muito, muito tempo, existiam $n$ cidades e $m$ linhas ferroviárias num reino. Cada linha continha muitas cidades, e cada cidade situava-se em exatamente uma linha ferroviária. Como algumas cidades não estavam ligadas por uma linha ferroviária, as pessoas enfrentavam frequentemente uma viagem árdua para ir de uma cidade a outra. As dificuldades de transporte tinham prejudicado muito o desenvolvimento económico do reino, pelo que o rei decidiu rapidamente abrir várias rotas aéreas.

Sob as suas ordens, as cidades foram divididas em $k$ distritos, permitindo às pessoas viajar de balão de ar quente entre quaisquer duas cidades do mesmo distrito. Além disso, para viajar para qualquer outra cidade, os habitantes podiam combinar comboios e balões de ar quente sem utilizar outros meios de transporte, o que também contribuiu para a prosperidade contínua da economia.

O rei queria saber se a sua política tinha beneficiado toda a gente. Contudo, morreu sem o descobrir, pois era necessária uma enorme quantidade de cálculos. Agora que a capacidade de cálculo melhorou, o problema volta a ser colocado. Supondo que viajar diretamente de uma cidade a outra de balão de ar quente demora uma hora, e que viajar de uma cidade para uma cidade adjacente numa linha ferroviária também demora uma hora, deves determinar o tempo médio necessário para viajar de uma cidade a outra usando apenas estes dois meios de transporte e indicar o produto de $\frac{n(n-1)}{2}$ por esse valor médio. Esse produto deverá ser um inteiro.

Para evitar dados de entrada enormes, cada cidade é representada por uma das primeiras $k$ letras minúsculas, representando uma estação de uma linha ferroviária, de modo que as cidades representadas pela mesma letra pertencem ao mesmo distrito.

Entrada

A entrada contém vários casos de teste. A primeira linha contém um inteiro $T$ que indica o número de casos de teste. Segue-se a descrição de todos os casos. Para cada caso:

A primeira linha contém três inteiros $n$, $m$ e $k$.

Cada uma das $m$ linhas seguintes contém uma cadeia não vazia, composta pelas primeiras $k$ letras minúsculas, que descreve por ordem as estações de uma linha ferroviária.

• $1 \le T \le 1000$
• $1 \le m \le n \le 10^6$
• $1 \le k \le 16$
• Cada distrito contém pelo menos uma cidade.
• A soma de $n$ em todos os casos de teste não excede $5 \times 10^6$.
• Existem no máximo 5 casos de teste com $k > 8$.

Saída

Para cada caso de teste, escreve uma linha com Case #x: y (sem aspas), em que $x$ é o número do caso de teste, começando em 1, e $y$ é a resposta (em horas) para esse caso.

Exemplos

Entrada 1

3
2 1 2
ab
2 2 1
a
a
5 2 3
abb
ac

Saída 1

Case #1: 1
Case #2: 1
Case #3: 20