열차 시간표 (Small)

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

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

열차 시간표에는 A역과 B역 사이를 오가는 모든 열차의 출발시각과 도착시각이 적혀 있다. 철도회사는 시간표대로 열차를 운행시키려면 하루가 시작될 때 A역과 B역에 각각 몇 대의 차량을 세워 두어야 하는지 알아야 한다. 어떤 역에서 열차가 출발하려면 그 역에 출발 준비를 마친 차량이 있어야 한다. 출발 준비를 마친 차량은 하루가 시작될 때 그 역에 세워 둔 차량이거나, 반대쪽 역에서 그 역으로 도착한 뒤 회차시간을 채운 차량이다.

두 역 사이 선로에는 대피선이 있으므로 열차가 반드시 출발한 순서대로 도착할 필요는 없다. 시간표에 적혀 있는 열차 외에는 어떤 열차도 운행하지 않는다.

시간표를 그대로 지키기 위해 A역에 세워 두어야 하는 차량의 최소 개수와 B역에 세워 두어야 하는 차량의 최소 개수를 구하라.

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

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

열차 정보가 담긴 각 줄에는 출발시각과 도착시각이 HH:MM 형식으로 공백 하나로 구분되어 주어진다. 모든 열차의 출발시각은 도착시각보다 이르고, 모든 출발과 도착은 같은 하루 안에서 일어난다. 시와 분은 모두 두 자리로 적으며 빈 자리는 0으로 채우고, 00:00부터 23:59까지의 24시간제를 쓴다.

제한

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

각 테스트 케이스마다 한 줄에 Case #x: a b 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $a$는 A역에, $b$는 B역에 하루가 시작될 때 세워 두어야 하는 차량의 최소 개수이다. $a$와 $b$는 공백 하나로 구분한다.