描述

经营一个出租车站点并非易事。除了显而易见的需要集中调度出租车以尽快接送打电话叫车的顾客之外，还需要安排所有已经提前预订的出租车行程。给定一个列表，包含次日所有预订的出租车行程，你希望最小化完成所有行程所需的出租车数量。

为了简化问题，我们将城市建模为一个矩形网格。城市中的一个地址用两个整数表示：街道号和大道号。从地址 $(a, b)$ 到地址 $(c, d)$ 乘坐出租车所需的时间是 $|a - c| + |b - d|$ 分钟。如果某次预订行程是出租车当天的第一趟行程，或者出租车能够在新行程预定出发时间至少一分钟之前到达新行程的起始地址，则出租车可以执行该预订行程。请注意，某些行程可能会持续到午夜之后。

输入

输入的第一行是一个正整数 $N$，表示接下来的测试场景数量。每个场景以一行包含整数 $M$ 开始，其中 $0 < M < 500$，表示预订的出租车行程数量。接下来的 $M$ 行描述了这些行程。每趟行程由出发时间（格式为 hh:mm，范围从 00:00 到 23:59）、两个整数 $a$ 和 $b$（表示起始地址的坐标）以及两个整数 $c$ 和 $d$（表示目的地址的坐标）描述。所有坐标至少为 0 且严格小于 200。每个场景中的预订行程按出发时间的升序排列。

输出

对于每个场景，输出一行，包含完成所有预订行程所需的最少出租车数量。

输入数据 1

2  
2  
08:00 10 11 9 16  
08:07 9 16 10 11  
2  
08:00 10 11 9 16  
08:06 9 16 10 11

输出数据 1

1  
2

来源

2004年西北欧