Zadanie

Gabrielova vyhodená figúrka

Počet bodov: 50, časový limit: 400ms

Gabrielovi nedávajú večer spať dve veci. Za prvé si uvedomil, že v KSP sa nikoho krstné meno nezačína na G, čo spôsobuje ťažkosti pri pomenúvaní úloh. Za druhé, dnes po škole hral niekoľko partií šachu s Gustávom, a ten mu v každej povedal výrok v tvare

‘Figúrkou f ktorá je na políčku x,y ti čoskoro vyhodím figúrku F ktorá je na políčku X,Y!’

Už si nepamätá, či sa to Gustávovi naozaj podarilo, ale výroky si pamätá dobre. Zaujíma ho však koľko ťahov dopredu si Gustáv musel premyslieť aby vedel vyriecť daný výrok – teda koľko najmenej ťahov by museli hráči spraviť, aby sa obe figúrky ocitli na rovnakom políčku.

Vstup a výstup

V prvom riadku je číslo \(T\) – počet partií šachu. Nasleduje \(T\) Gustávovich výrokov v tvare \(f~x~y~F~X~Y\). \(0 \leq f,F \leq 4\) označujú typy figúrok, v poradí Kráľ, Kôň, Kráľovná, Veža, Strelec. \(0 \leq x,y,X,Y \leq 7\) označujú políčka, na ktorých sa figúrky nachádzajú.

Pre každý výrok povedzte jedno číslo – najmenší počet ťahov, po ktorých by sa figúrky mohli ocitnúť na rovnakom políčku. V tejto úlohe sa mohol jeden z hráčov pohnúť aj viackrát za sebou, a taktiež ignorujeme to že kráľ by sa nemal posunúť na ohrozované políčko.

Ak sa figúrky nikdy nemôžu dostať na rovnaké políčko, vypíšte namiesto čísla reťazec ‘INF’.

V prvej sade \(T \leq 101\). V druhej \(T \leq 102\,400\).

Príklad

Input:

10
2 3 6 1 6 2
3 3 6 3 6 7
4 4 6 4 2 4
3 6 0 4 1 0
3 7 1 3 5 2
0 0 6 1 5 4
0 5 7 3 3 5
0 4 1 4 5 3
3 2 1 3 4 2
0 5 2 0 2 7

Output:

2
2
1
1
2
3
2
2
2
5