/**
题目：Taxi Cab Scheme UVALive - 3126 最小路径覆盖解法(必须是DAG，有向无环图) = 结点数-最大匹配
链接：https://vjudge.net/problem/UVALive-3126
题意：lv lrj训练指南P357 思路：最小路径覆盖(必须是DAG，有向无环图) = 结点数-最大匹配
最小路径覆盖：就是在图中找尽量少的路径，使得每个节点恰好在一条路径上（不同的路径不能有公共点），单独的结点也可以作为一条路径。 时间是一个天然的序，因此可以构图G如下：每个客人是一个节点，如果同一个出租车在接完客人u以后还来得及接客人v.连边 u->v。不难发现这是一个DAG。
并且它的最小路径覆盖就是本题的答案。 DAG最小路径覆盖的解法如下：把所有结点拆为X结点i和Y结点i'，如果图G中存在有向边i->j，那么则在二分图中引入i->j'。设二分图的最大匹配数是m，则结果就是
n-m; 这里的n不是拆点之后的点数，而是原先的G图点数。 */ #include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
const int MAXN = ;
int f[MAXN][MAXN];
int vit[MAXN], S[MAXN], T[MAXN];
int N;
///模板
bool Find(int x)///走交替路，寻找增广路
{
for(int i = ; i <= N; i++){///n表示右侧点数。
if(f[x][i]&&vit[i]==){
vit[i] = ;
if(T[i]==||Find(T[i])){
T[i] = x;///右边第i个点和左边第x个点匹配成功。
S[x] = i;///左边第x个点和右边第i个点匹配成功。
return true;
}
}
}
return false;
}
struct node
{
int sx, sy;
int ex, ey;
int hour, minute;
int time;
}client[MAXN];
int main()
{
int n, m, k;
cin>>k;
while(k--){
scanf("%d",&n);
N = n*;
for(int i = ; i <= n; i++){
scanf("%d:%d%d%d%d%d",&client[i].hour,&client[i].minute,&client[i].sx,&client[i].sy,&client[i].ex,&client[i].ey);
client[i].time = client[i].hour*+client[i].minute+abs(client[i].sx-client[i].ex)+abs(client[i].sy-client[i].ey);
}
memset(f, , sizeof f);
for(int i = ; i <= n; i++){///拆点x， x,x+n;
for(int j = ; j <= n; j++){
if(i==j) continue;
if(client[i].time+abs(client[i].ex-client[j].sx)+abs(client[i].ey-client[j].sy)+<=client[j].hour*+client[j].minute){
f[i][j+n] = ;
}
}
} int ans = ;
memset(T, , sizeof T);
memset(S, , sizeof S);
///模板
for(int i = ; i <= N; i++){
memset(vit, , sizeof vit);
if(Find(i)) ans++;
}
printf("%d\n",n-ans);
}
return ;
}