SPOJ Brasil

Gabriel Garcia Marques é um escritor colombiano autor de histórias fantásticas como "Cién años de soledade", "El amor en los tiempos del cólera" e "Memoria de mis putas tristes". Suas histórias se caracterizam pelo uso do que ficou conhecido como "realismo mágico", em que situações reais são explicadas com elementos mágicos. Apesar de seus trabalhos serem considerados muito ricos e até cenográficos, livros baseados em suas obras não têm merecido sucesso de público ou de crítica. O mais recente exemplo foi a filmagem em 2007 de "Love in the Time of Cholera".

Uma de suas obras menos conhecidas é "Los buses de Cartagena", que descreve a história de uma pequena companhia de ônibus da cidade colombiana que, principalmente devido aos problemas de quebra dos ônibus por excesso de carga, pretendia reduzir o número de passageiros transportados em cada viagem de Cartagena a Medellin para um mesmo número fixo. Ao mesmo tempo, a companhia queria continuar atendendo a todos os pedidos de forma satisfatória. Cada ônibus possui um horário de partida, e cada passageiro dispõe de uma lista de horários nos quais gostaria de viajar. Os passageiros desejam apenas ir para Medellin, ou seja, nenhum passageiro pretende viajar duas vezes no mesmo dia.

Sua tarefa é determinar o número mínimo de passageiros que devem ser transportados em cada viagem respeitando a restrição de que todos os passageiros devem ser atendidos.

Entrada

A primeira linha de um caso de testes terá um inteiro T que indicará o número de instâncias. A primeira linha de cada instância contém dois inteiros N e M (1 ≤ N, M ≤ 100). Cada uma das M linhas seguintes possui o horário de partida de um dos ônibus. O horário está no formato hh:mm (00 ≤ hh ≤ 23, 00 ≤ mm ≤ 59 e hh e mm possuem dois dígitos). Cada uma das N linhas seguintes contém a lista de horários em que cada passageiro pode viajar. A lista dos horários está no seguinte formato: um inteiro K (1 ≤ K ≤ M) seguido de K horários, também no formato hh:mm, separados por um espaço em branco.

Saída

Para cada instância imprima uma linha contendo o número mínimo de passageiros que devem ser transportados.

Exemplo de entrada
3
3 2
00:10
11:30
1 00:10
2 00:10 11:30
2 11:30 00:10
3 3
23:50
23:50
23:51
2 23:51 23:50
1 23:50
1 23:50
4 2
10:00
12:01
1 12:01
1 12:01
1 12:01
1 12:01

Exemplo de saída
2
1
4