열차 시간표 (Large)

어떤 철도 노선에 A역과 B역, 두 역만 있다.

열차는 하루 동안 A역에서 B역으로, 그리고 B역에서 A역으로 여러 번 운행한다. 열차가 A역에서 B역으로(또는 B역에서 A역으로) 이동해 도착하면, 반대 방향으로 다시 출발하기까지 회차시간이 필요하다. 예를 들어 열차가 12:00에 도착하고 회차시간이 0분이면 그 열차는 12:00에 곧바로 출발할 수 있다.

시간표에는 A역과 B역 사이를 오가는 모든 열차의 출발 시각과 도착 시각이 적혀 있다. 철도회사는 시간표대로 운행하려면 하루가 시작될 때 A역과 B역에 각각 몇 대의 차량을 미리 세워 두어야 하는지 알아야 한다. 어떤 열차가 A역이나 B역을 출발하려면 그 시각에 출발 준비를 마친 차량이 그 역에 있어야 한다. 두 역 사이 선로에는 대피선이 있어서 열차가 출발한 순서대로 도착할 필요는 없다. 시간표에 적힌 열차 외에 다른 열차는 운행하지 않는다.

A역과 B역에 미리 세워 두어야 하는 차량의 최소 개수를 각각 구하라.

첫 줄에 테스트 케이스의 개수 $N$이 주어진다.

각 테스트 케이스는 여러 줄로 이루어진다. 첫 줄에는 회차시간 $T$가 분 단위로 주어진다. 다음 줄에는 A역에서 B역으로 가는 열차의 수 $N_A$와 B역에서 A역으로 가는 열차의 수 $N_B$가 공백으로 구분되어 주어진다. 이어지는 $N_A$개의 줄에는 A역에서 B역으로 가는 열차의 정보가 한 줄에 하나씩 주어진다.

각 줄에는 출발 시각과 도착 시각이 HH:MM 형식으로 공백을 두고 주어진다. 모든 열차의 출발 시각은 도착 시각보다 이르고, 모든 출발과 도착은 같은 날 안에 일어난다. 시와 분은 모두 두 자리로 쓰며 빈자리는 0으로 채우고, 00:00부터 23:59까지의 24시간제 표기를 쓴다.

$N_A$개의 줄 뒤에는 B역에서 A역으로 가는 열차의 출발 시각과 도착 시각이 같은 형식으로 $N_B$개의 줄에 주어진다.

제한

• $1 \le N \le 100$
• $0 \le N_A, N_B \le 100$
• $0 \le T \le 60$

각 테스트 케이스마다 한 줄에 Case #x: 를 먼저 출력하고, 그 뒤에 A역에 미리 세워 두어야 하는 차량의 수와 B역에 미리 세워 두어야 하는 차량의 수를 공백으로 구분해 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다.