Grupa saperów dostała nowe zadanie. Muszą bardzo szybko dotrzeć do potężnych bomb umieszczonych
na polach minowych. Nikt nie wie kiedy bomby wybuchną więc trzeba to zrobić w jak najkrótszym czasie,
zanim eksplodują i zniszczą całą okolice. Na szczęście saperzy są w posiadaniu planów pól minowych,
co bardzo ułatwia sprawę.
Zostałeś poproszony o pomoc w tym arcytrudnym i skomplikowanym zadaniu.
Dysponujesz planami pól minowych. Dla każdego pola musisz wyznaczyć jak najkrótszą bezpieczną ścieżkę
z miejsca, w którym można wejść na pole do miejsca, w którym znajduje się bomba. Wiadomo, że zawsze
istnieje taka ścieżka.
Wszystkie pola minowe mają kształt kwadratu. Pola są podzielone na małe obszary. W każdym obszarze dostępna jest informacja czy znajduje się na nim mina czy nie. Saper może poruszać się tylko między sąsiądującymi ze sobą obszarami tylko w poziomie i w pionie. Obszar, na którym można rozpocząć wędrówkę po polu (obszary startowe) mogą znajdować nawet w środku pola minowego. Jest to spowodowane bardzo dużym pofałdowaniem terenu.
Dla każdego pola minowego wyznacz minimalną długość ścieżki (mierzoną w liczbie przebytych obszarów) łączącej start z bombą. Scieżka musi prowadzić przez obszary bez min.
W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba naturalna określająca liczbę pól minowych, których opisy pojawią się
dalej na wejściu.
Każde pole minowe opisane jest: w pierwszym wierszu, przez jedną liczbę N
(2 ≤ N ≤ 10), określającą rozmiar pola.
W kolejnych N wierszach i N kolumnach opisane są obszary pola minowego.
Obszar o współrzednych (X,Y) opisany jest przez cyfrę
znajdującą się w X-tej kolumnie Y-tego wiersza.
Jeżeli obszar jest pusty opisany jest przez "0", jeżeli jest na nim mina - "1",
jeżeli jest to obszar startowy - "2", jeżeli jest na nim bomba - "9".
Dla każdego pola minowego podaj minimalną liczbę obszarów, jaką trzeba pokonać żeby bezpiecznie dostać sie ze startu do bomby.
2 3 1 9 0 2 1 0 0 0 0 2 9 2 0 0
6 1