Jest rok 4096. Jakiś czas temu w układzie słonecznym odkryto planetę XoX. Ma ona ciekawą właściwość: ze wzglądu na to, że ruch obrotowy wokół jej osi kompensuje ruch dookoła słońca, jedna połowa planety jest zawsze zacieniona. Rozpoczęto przygotowania, które mają na celu zbadanie tej ciemnej strony. Kto wie, co tam jest? Napotkano jednak na problem zasilania lądowników - te działają dzięki energii słonecznej.
Na podstawie pomiarów wykonanych z przestrzeni kosmicznej udało się jednak odwzorować na mapach topografię terenu planety XoX. Co więcej, odkryto, że gdzieniegdzie znajdują się fosforyzujące skały, które mogą służyć do ładowania lądownika. Jest więc jakiś postęp! Sporządzono szczegółowe mapy terenu i przeprowadzono skomplikowane obliczenia.
Mapa badanego obszaru ma n wierszy i m kolumn, co daje nam n*m kwadratowych obszarów (każdy w rzeczywistości ma rozmiar metr na metr). Rzeźba terenu jest urozmaicona i każdy obszar jest położony na pewnej wysokości: kwadrat odwzorowany na mapie w i-tym wierszu i j-tej kolumnie (1 ≤ i ≤ n; 1 ≤ j ≤ m) leży na wysokości hi;j. W związku z tym, badany teren został przybliżony jako prostopadłościany o różnych wysokościach, z których każdy ma podstawę metr na metr. Na tym terenie są dwa obszary, na których znajdują się fosforyzujące kryształy. Lądownik rozpoczyna swoją misję w pierwszym z nich i musi dostać się do drugiego.
Są jednak duże ograniczenia. Lądownik może się poruszać z danego obszaru do czterech sąsiednich obszarów: na wschód, zachód, północ i południe, a więc nie umie jeździć po przekątnej. Co więcej, nie może on przejechać do sąsiedniego obszaru jeśli ten jest ponad metr wyżej lub ponad 3 metry niżej niż obszar, na którym jest aktualnie. Pozostaje jeszcze kwestia ładowania. Pojemność baterii starcza na jeden dzień - tyle potrzebuje lądownik, by przejść z jednego obszaru na sąsiedni (badając je przy okazji). W związku z tym, na każdym odwiedzonym obszarze (z wyjątkiem początkowego i końcowego) lądownik musi ładować baterie. Aby to było możliwe, promień światła przynajmniej jednego z fosforyzujących kryształów musi wówczas dosięgać do jego baterii słonecznej.
Założono, że lądownik w czasie próby ładowania znajduje się dokładnie na środku kwadratowego obszaru, a jego bateria słoneczna jest pół metra nad gruntem. Ustalono też, że fosforyzujące kryształy również znajdują się na środku swoich obszarów i mają wysokość pół metra (z takiej wysokości fosforyzują). Źródła światła i baterię słoneczną należy traktować więc jako punkty położone pół metra nad środkiem kwadratów. Dodatkowo, skały (czyli prostopadłościany) nie przepuszczają promieni z kryształu, ani ich nie odbijają. Promień może natomiast się stykać z ich krawędziami przenikając dalej (w szczególności przejdzie też między dwoma prostopadłościanami stykającymi się tylko bocznymi krawędziami).
Napisz program, który na podstawie wczytanej mapy wyznaczy liczbę dni, jaka zajmie lądownikowi przejście najkrótszej trasy (o ile taka w ogóle istnieje) z jednego fosforyzującego obszaru do drugiego (czas ładowania baterii jest krótki i można go pominąć).
Wejście
Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1 ≤ N ≤ 20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:
Jeden zestaw danych
W pierwszej linii każdego zestawu podane są wymiary mapy n oraz m (1 ≤ n; m ≤ 200) oddzielone spacją. W kolejnych n liniach mamy po m liczb całkowitych oznaczających wysokość danego obszaru. Wysokość obszaru o współrzędnej (i, j ) na mapie (czyli hi;j ) jest liczbą całkowitą należącą do przedziału <0, 500>. W ostatniej linii każdego testu podane są cztery liczby całkowite: w1 , k1 , w2 , k2 (1 ≤ w1; w2 ≤ n; 1 ≤ k1; k2 ≤ m) oznaczające współrzędne na mapie dwóch różnych obszarów, na których są fosforyzujące kryształy. Litera w oznacza tutaj numer wiersza, natomiast litera k to numer kolumny.
Wyjście
Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu ma być liczba dni potrzebna lądownikowi do przebycia najkrótszej drogi z pierwszego obszaru do drugiego. Jeśli nie istnieje droga dla lądownika między dwoma wskazanymi obszarami, to program ma wypisać -1.
Przykład
Dane wejściowe
3
3 3
1 2 8
7 3 9
8 4 3
1 1 3 3
4 6
2 1 1 2 3 4
1 0 1 0 4 5
8 7 9 9 5 5
1 1 1 1 3 5
1 1 4 1
5 5
8 7 6 5 4
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
1 1 5 1
Wynik
4
-1
10
