열차 시간표

한 철도 노선에 A와 B라는 두 역이 있다. 열차는 하루 동안 A에서 B로 또는 B에서 A로 여러 번 운행할 수 있다. 열차가 A에서 출발해 B에 도착하면(또는 B에서 출발해 A에 도착하면), 돌아가는 운행을 시작할 준비가 되기까지 일정한 시간이 필요하다. 이를 회차 시간이라고 한다. 예를 들어 열차가 12:00에 도착하고 회차 시간이 0분이면, 12:00에 즉시 출발할 수 있다.

열차 시간표에는 A와 B 사이를 운행하는 모든 편의 출발 시각과 도착 시각이 명시되어 있다. 철도 회사는 시간표대로 운행하기 위해 하루를 시작할 때 A와 B에 각각 몇 대의 열차가 있어야 하는지 알아야 한다. 즉, 열차가 A 또는 B에서 출발하도록 예정된 때마다 실제로 그곳에 출발할 준비가 된 열차가 한 대 있어야 한다. 선로에는 열차가 서로 지나갈 수 있는 구간이 있으므로, 열차가 반드시 출발한 순서대로 도착하지는 않는다. 열차는 시간표에 나타나지 않은 편을 운행할 수 없다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 20 0 ≤ NA, NB ≤ 20 0 ≤ T ≤ 5

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 100 0 ≤ NA, NB ≤ 100 0 ≤ T ≤ 60

입력의 첫 줄에는 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다.

각 케이스는 여러 줄로 이루어진다. 첫 줄에는 분 단위의 회차 시간 T가 주어진다. 다음 줄에는 NA와 NB라는 두 수가 주어진다. NA는 A에서 B로 가는 편의 수이고, NB는 B에서 A로 가는 편의 수이다. 그다음에는 A에서 B로 가는 편의 세부 정보를 나타내는 NA개의 줄이 주어진다.

각 줄에는 두 필드가 있으며, 해당 편의 출발 시각과 도착 시각이 HH:MM 형식으로 주어진다. 각 편의 출발 시각은 도착 시각보다 이르다. 모든 도착과 출발은 같은 날에 이루어진다. 운행 편은 어떤 순서로든 나타날 수 있으며, 반드시 시각순으로 정렬되어 있지는 않다. 시와 분 값은 모두 앞을 영으로 채운 두 자리이며, 24시간제 시계의 시각이다(00:00부터 23:59까지).

이 NA개 줄 다음에는 B에서 A로 가는 편의 출발 시각과 도착 시각을 나타내는 NB개의 줄이 주어진다.

각 테스트 케이스마다 "Case #x: " 뒤에 A에서 하루를 시작해야 하는 열차의 수와 B에서 하루를 시작해야 하는 열차의 수를 차례로 적은 한 줄을 출력한다.