병원 대기열

온갖 이상한 바이러스가 퍼지면서, 국제 리볼버 애호가 연맹(ICORE)의 모든 회원은 분기마다 종합병원에서 신체검사를 받아야 한다. 모든 검사는 상사가 배정하며 같은 날에 진행된다. 각 회원은 다음 정보를 담은 안내를 받는다.

• 집합 {1, ..., n} 중 하나인 자신의 번호
• 종합병원에 도착해야 하는 시각
• 방문해야 하는 진료실 목록(주어진 순서대로 방문)

진료실은 {1, ..., m} 번호로 구분된다.

모두 일정이 전문적으로 짜여 줄을 서서 기다릴 일이 없다고 들었지만, 실제로는 줄이 빠르게 생겼다. 회원들은 모두 규율이 잘 잡혀 있어 다음 규칙을 따른다.

• 회원이 시각 t에 도착하기로 되어 있으면, 시각 t에 자신의 목록 첫 번째 진료실 앞에 나타난다.
• 여러 사람이 같은 시각 t에 한 진료실에 도착하면, 번호가 작은 순서대로 줄을 서며, 먼저 도착한 사람들이 이미 만든 줄의 끝에 붙는다.
• 시각 t에 진료실 x 앞에 t 이전 또는 t에 도착한 사람들의 줄이 있으면, 줄의 맨 앞 사람이 진료실 x에 들어간다. 이 사람은 한 단위 시간 뒤에 진료실을 나와 시각 t+1에 목록의 다음 진료실 앞에 나타나며, 같은 순간에 줄의 다음 사람이 진료실 x에 들어간다.
• 시각 t의 진료실 x 방문이 그 방문자의 마지막 방문이었다면, 시각 t+1에 그 방문자는 병원을 떠난다.

마지막 방문자가 병원을 떠나는 시각을 구하라.

첫째 줄에 테스트 케이스의 수를 나타내는 자연수 c가 주어진다. 이후 각 테스트 케이스가 아래 형식으로 이어진다.

각 케이스의 첫 줄에는 두 자연수 n과 m (1 ≤ n, m ≤ 1000)이 주어지며, 각각 방문자 수와 진료실 수를 뜻한다. 이어지는 n개의 줄은 각각 한 명의 방문자를 나타낸다. i번째 줄 (1 ≤ i ≤ n)은 다음 형식을 가진다.

t k g_1 g_2 ... g_k

이는 방문자 i가 시각 t에 도착하여 g_1, g_2, ..., g_k 순서로 k개의 진료실을 방문해야 함을 의미하며, 1 ≤ g_j ≤ m이다. 0 ≤ t ≤ 1000000이고, 하루에 예정된 방문의 총수는 1000000을 넘지 않음이 보장된다.

각 테스트 케이스마다 마지막 방문자가 병원을 떠나는 시각을 한 줄에 출력한다.