Prevádzkovanie taxíkov nie je také jednoduché, ako by sa mohlo zdať. Okrem zjavnej potreby centrálnej koordinácie taxíkov, aby mohli vyzdvihnúť zákazníkov, ktorí volajú a chcú sa dostať k taxíku čo najskôr, je tu aj potreba naplánovať všetky jazdy taxíkom, ktoré boli rezervované vopred. Keď máte zoznam všetkých rezervovaných jázd na nasledujúci deň, chcete minimalizovať počet taxíkov potrebných na vykonanie týchto jázd.
Zjednodušene modelujeme mesto ako obdĺžnikovú mriežku. Adresa v meste je označená dvoma celými číslami: číslom vodorovnej a číslom zvislej ulice. Čas potrebný na prevoz taxíkom z adresy $a$, $b$ na $c$, $d$ je $|a-c| + |b-d|$ minút. Taxík môže vykonať rezervovanú jazdu, ak je jeho prvou jazdou v daný deň, alebo ak sa dokáže dostať z jeho poslednej polohy na zdrojovú adresu novej jazdy aspoň o jednu minútu skôr, než je naplánovaný odchod novej jazdy. Všimnite si, že niektoré jazdy môžu skončiť až po polnoci.
V prvom riadku vstupu je jedno kladné celé číslo $N$, ktoré udáva počet testovacích scenárov, ktoré nasledujú. Každý scenár sa začína riadkom obsahujúcim jedno celé číslo $M$, kde $0 < M < 500$, pričom $M$ je počet rezervovaných jázd. Nasledujúcich $M$ riadkov obsahuje jazdy. Každá jazda je opísaná odchodovým časom v tvare \texttt{hh:mm} (od 00:00 do 23:59), dvoma celými číslami $a$, $b$, ktoré sú súradnice zdrojovej adresy, a dvoma celými číslami $c$, $d$, ktoré sú súradnice cieľovej adresy. Všetky súradnice sú aspoň $0$ a striktne menšie než $200$. Rezervované jazdy v každom scenári sú zoradené v poradí narastajúceho času odchodu.
Pre každý scenár vypíšte jeden riadok obsahujúci minimálny počet taxíkov potrebných na vykonanie všetkých rezervovaných jázd.
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