题目描述

经营出租车站并不那么简单。除了显而易见的需要集中协调出租车以尽快接到呼叫要求乘坐出租车的乘客之外，还需要安排所有提前预订的出租车行程。给定下一天所有已预订出租车行程的列表，你希望最小化需要的出租车数量来完成所有行程。

为了简化起见，我们将城市建模为一个矩形网格。城市中的一个地址由两个整数表示：街道号和大道号。乘坐出租车从地址 $a,b$ 到 $c, d$ 所需的时间为 $|a - c| + |b - d|$ 分钟。如果一辆出租车是当天的第一次行程，或者它可以在最新行程的出发时间前至少一分钟到达新行程的出发地址，那么它可以执行预订的行程。请注意，一些行程可能在午夜后结束。

输入格式

输入的第一行是一个正整数 $N$，表示接下来的测试场景数。

每个场景以包含一个整数 $M$ 的行开始，表示预订的出租车行程数量。接下来的 $M$ 行包含这些行程。每个行程由一个格式为 $hh:mm$ 的出发时间描述（范围从 $00:00$ 到 $23:59$ ），两个整数 $a$ 和 $b$ 表示出发地址的坐标，以及两个整数 $c$ 和 $d$ 表示目的地地址的坐标。所有坐标至少为 $0$，严格小于 $200$。每个场景中的预订行程按出发时间递增的顺序排序。

输出格式

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

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
2

样例分析

如上所述。

数据范围与提示

对于$100 \%$ 的数据：$0 < N < 10$ ，$0 < M < 500$。