택시 배차 계획

택시 회사를 운영하는 일은 생각보다 간단하지 않습니다. 지금 당장 택시를 부르는 손님을 최대한 빨리 태우기 위한 중앙 배차도 필요하지만, 미리 예약된 모든 운행을 어떻게 배정할지도 계획해야 합니다. 다음 날 예약된 모든 택시 운행 목록이 주어질 때, 모든 운행을 처리하는 데 필요한 택시의 최소 대수를 구하세요.

문제를 단순화하기 위해 도시를 직사각형 격자로 모형화합니다. 도시의 한 주소는 두 정수, 즉 거리(street) 번호와 대로(avenue) 번호로 나타냅니다. 주소 $(a, b)$ 에서 주소 $(c, d)$ 까지 택시로 이동하는 데 걸리는 시간은 $|a - c| + |b - d|$ 분입니다. 어떤 택시가 예약된 운행을 맡을 수 있는 경우는 다음 두 가지입니다. 그 운행이 그날 이 택시의 첫 운행이거나, 또는 이 택시가 직전 운행의 도착지에서 새 운행의 출발지까지 이동하여 새 운행의 예정 출발 시각보다 적어도 1분 일찍 도착할 수 있는 경우입니다. 일부 운행은 자정을 넘겨 끝날 수도 있습니다.

입력의 첫 줄에는 이어지는 시나리오의 개수인 양의 정수 $N$ 이 주어집니다. 각 시나리오는 예약된 택시 운행의 수 $M$ ($0 < M < 500$) 이 적힌 줄로 시작합니다. 이어지는 $M$ 개의 줄에는 각 운행이 주어집니다. 각 운행은 hh:mm 형식의 출발 시각(00:00 부터 23:59 까지), 출발지 주소의 좌표를 나타내는 두 정수 $a$ $b$, 도착지 주소의 좌표를 나타내는 두 정수 $c$ $d$ 로 기술됩니다. 모든 좌표는 0 이상 200 미만입니다. 각 시나리오의 예약 운행은 출발 시각이 증가하는 순서로 정렬되어 있습니다.

각 시나리오마다, 예약된 모든 택시 운행을 처리하는 데 필요한 최소 택시 대수를 한 줄에 출력하세요.