Državno natjecanje iz informatike 2016. / Druga podskupina (3. i 4. razred) – Drugi dan natjecanja - 1. zadatak

Mirko se nalazi u ogromnom gradu u kojem gradski blokovi skupa sa ulicama i avenijama čine beskonačnu pravokutnu mrežu.

Avenije se pružaju smjerom sjever-jug te su označene uzastopnim cijelim brojevima koji rastu prema istoku.

Sve avenije su jednosmjerne – ako je avenija označena parnim brojem onda se njome može voziti samo prema sjeveru, a inače prema jugu.

Ulice se pružaju smjerom istok-zapad te su označene uzastopnim cijelim brojevima koji rastu prema sjeveru.

Sve ulice su jednosmjerne – ako je ulica označena parnim brojem onda se njome može voziti samo prema istoku, a inače prema zapadu.

Presjeke avenija i ulica nazivamo križanja te svako križanje označavamo parom brojeva (x, y), gdje je x broj avenije, a y broj ulice.

Zadano je n parova križanja, za svaki par križanja a, b odredite duljinu najkraćeg puta od križanja a do križanja b.

Duljina puta je jednaka ukupnom broju križanja na putu brojeći završno križanje b, ali ne i početno križanje a.

Ulazni podaci

U prvom redu nalazi se prirodni broj n (n ≤ 1000) – broj parova križanja.

U svakom od sljedećih n redova nalaze se četiri cijela broja xa, ya, xb, yb (−108 ≤ xa, ya, xb, yb ≤ 108 ) – koordinate (broj avenije i broj ulice) početnog i završnog križanja.

Početno i završno križanje su uvijek različiti.

Izlazni podaci

Ispišite n redova. U k-ti red ispišite duljinu najkraćeg puta za k-ti po redu par križanja s ulaza.

Primjer zadatka

ULaz

6
0 0 -1 0
0 0 1 0
-1 -1 2 2
-1 -1 1 1
-1 -1 2 1
2 1 -1 -1

Izlaz

3
1
8
8
7
5