SPOJ Brasil

O Eurovision Song Contest (ESC) é uma competição anual de canções. Cada país da Europa (e mais alguns países convidados, como Israel) apresenta uma música e, então, há uma votação para determinar qual é a pior delas. Como punição, o país “vencedor” é obrigado a organizar o concurso no ano seguinte.

O ESC é pouco conhecido fora da Europa, mas ainda assim é um dos eventos não-esportivos mais assistidos do planeta. Nesse ano, 150 milhões de pessoas assistiram a “vitória” do Azerbaijão, que chocou muita gente que não lembrava que tal país ficava na Europa (ou mesmo que ele existia). A vitória foi cercada de suspeitas, porém, pois muita gente considera que Popular, da Suécia, era uma música muito, muito pior.

Na etapa final do concurso, os diversos países que se classificaram apresentam suas músicas, em ordem que devia ser aleatória. Porém, alguns países se recusam a se apresentar logo antes (ou depois) de certos outros países, por motivos geopolíticos que não vem ao caso. Considerando que não levar em conta essas inimizades poderia provocar uma guerra, e que seria ridículo causar uma guerra por conta de um concurso musical, os organizadores decidiram que a ordem dos países na final deve, obrigatoriamente, obedecer às vontades dos países. Mais especificamente, eles decidiram que de todas as ordenações possíveis que não deixam nenhum país “triste”, deve-se escolher uma aleatoriamente de forma uniforme.

Isso funcionou bem por vários anos, mas há rumores de que para o concurso de 2012 não haverá nenhuma ordem possível que satisfaça todos os países. Sua tarefa, aqui, é, dada a lista de países e seus “inimigos”, contar o número de ordens possíveis para a apresentação final que satisfazem todas as demandas.

Entrada

A entrada começa com uma linha contendo um inteiro T, o número de casos de teste (1 ≤ T ≤ 20). Em seguida, há T casos de teste.

Cada caso de teste começa com uma linha contendo um inteiro N, o número de países na final (1 ≤ N ≤ 9). Seguem N linhas descrevendo cada um desses países. Cada uma dessas N linhas começa com o nome do país (string de até 30 caracteres, contendo apenas letras minúsculas ou maiúsculas). Em seguida, separados por espaço em branco, há o número A de países aos quais aquele país não quer ser adjacente (0 ≤ A < N), e os nomes de cada um desses países.

Saída

Para cada caso de teste, imprima uma linha no formato Teste #x: y, onde x é o número do caso de teste (começando de 1) e y é o número de ordenações válidas para a final correspondente aquele caso de teste.

Exemplos

Entrada:
3
4
Azerbaijao 2 Italia Portugal
Italia 1 Portugal
Portugal 0
Espanha 1 Azerbaijao
3
Portugal 0
Espanha 0
Franca 1 Portugal
7
Inglaterra 1 Irlanda
Irlanda 1 Inglaterra
Noruega 0
Dinamarca 0
Suecia 0
Finlandia 0
Islandia 0

Saída:
Teste #1: 0
Teste #2: 2
Teste #3: 3600

No primeiro caso de teste, há quatro países. O Azerbaijão se recusa a se apresentar próximo a Portugal e Itália, e a Espanha se recusa a se apresentar próxima ao Azerbaijão. Assim, não há nenhum país que possa se apresentar logo antes (ou logo depois) do Azerbaijão e, portanto, há zero ordenações válidas.

No segundo caso de teste, a França se recusa a se apresentar próximo de Portugal, e, portanto, a Espanha tem necessariamente que separar os dois. Assim, há duas ordenações possíveis:

• Portugal, Espanha, França
• França, Espanha, Portugal

No terceiro caso de teste, há 7 países e todas as ordenações são válidas exceto aquelas que contém a Inglaterra adjacente à Irlanda. Há 7! = 5040 ordenações possíveis sem levar em conta a restrição, e, dessas, 6! · 2 = 1440 têm os dois países inimigos como adjacentes. Assim, há 5040 - 1440 = 3600 ordenações válidas.