Egy n*m-es téglalap alakú "sakktábla" egyik mezőjéről jussunk el egy másik mezőjére a lehető legkevesebb lóugrással. Adjuk meg, hogy hány lóugrás szükséges!

Bemenet:

• A teszteset első sora tartalmazza a tábla méretét, szóközzel elválasztott két pozitív egész szám formájában. Az első szám n megadja a tábla sorainak a számát, míg a második szám m a tábla oszlopainak a számát (1 <= n, m <= 1000)
• A következő sor tartalmazza a kérdések számát (N pozitív egész szám).
• Majd N soron keresztül jönnek a kérdések. Egy kérdés két mező adatait tartalmazza, hogy honnan-hová kell eljutni lóugrással. Először a kiindulási mező sor ill. oszlop koordinátái, majd a célmező sor és oszlop koordinátái vannak megadva szóközökkel elválasztva. (A tábla sorait és oszlopait értelemszerűen a [0..n-1] és [0..m-1] egészekkel azonosítjuk.)

Kimenet:

Minden teszteset esetén írjuk ki, hogy hányadik teszteset válaszai következnek. Majd soronként írjuk ki a teszteset kérdéseire adott válaszokat. A válasz kétféle lehet:

• Ha el lehet jutni lóugrással a kiindulási mezőről a célmezőre, akkor adjuk meg eljutáshoz szükséges lóugrások minimális számát.
• Amennyiben nem lehet eljutni lóugrással a kiindulási mezőről a célmezőre, akkor írjuk ki, hogy "Nem elerheto"

Példa:

Tesztfájl