AlgoLiga 2018

Ed gra w grę pt. Bombowa Ucieczka. W grze tej znajdujesz się na prostokątnej mapie o wymiarach n×m na polu (a,b) i musisz dostać się (uciec) na pole (c,d). Wszystko byłoby fajnie gdyby nie to, że niektóre pola wybuchają! Po polu które wybuchło nie można chodzić, a wejście na pole które w tej turze wybuchnie jest samobójstwem i powoduje przegraną. W jednej turze można się przemieścić jedynie na pole znajdujące się:

• powyżej
• poniżej
• z lewej strony
• z prawej strony

Ed właśnie po wielu godzinach zmagania się z grą przeszedł ostatni jej poziom. Ed zastanawia się teraz, ilu minimalnie polom z danej mapy wystarczyłoby zmienić licznik do wybuchu na 0, aby uniemożliwić jej przejście? Żeby nie było za łatwo, licznik musi zostać niezmieniony dla pola startowego i pola końcowego.

Wejście

W pierwszej linii liczba testów t ∈ [1;5].

Każdy test wygląda następująco:

W pierwszej linii dwie liczby n i m (n×m ∈ [2;100]) określające rozmiar mapy.

W każdym z kolejnych n wierszy znajduje się m liczb. Liczba x_ij ∈ [-1;10001] znajdująca się w i-tym wierszu i j-tej kolumnie oznacza, że pole znajdujące się w tej samej kolumnie i wierszu wybuchnie po x_ij turach. Jeśli x_ij jest równe -1, to pole nigdy nie wybuchnie. Pole startowe i końcowe zawsze ma ustawiony licznik na -1.

W następnej linii wejścia znajdują się cztery liczby a ∈ [1;m], b ∈ [1;n], c ∈ [1;m], d ∈ [1;n] oznaczające, że pole startowe znajduje się w a-tej kolumnie i b-tym wierszy, zaś docelowe w c-tej kolumnie i d-tym wierszu.

Wyjście

Dla każdego testu należy wypisać minimalną liczbę pól jakie należy usunąć, aby uniemożliwić przejście mapy. (Mapa może być niemożliwa do przejścia od początku). Jeśli nie da się tak usunąć niektórych pól, żeby uniemożliwić przejście mapy wypisz -1.

Przykład

Wejście:

1
3 3
-1 3 3
2 4 4
-1 5 -1
1 1 3 3

Wyjście:

2