AlgoLiga 2018

Pole minowe

Znajdujesz się na polu walki i otrzymałeś właśnie rozkaz, aby Twój oddział, znajdujący się w sektorze A, pomógł niezwłocznie oddziałowi znajdującemu się w sektorze B. Niestety teren może być zaminowany i nie zawsze możliwe jest dotarcie do sektora B, bez dodatkowych działań oczyszczających niektóre sektory z min. Na szczęście zwiad podesłał Ci aktualną mapę terenu z rozmieszczeniem min. Mapa to prostokątny diagram podzielony na sektory, które są albo zaminowane, albo nie. Pomiędzy sąsiednimi sektorami można poruszać się wyłącznie w czterech kierunkach: północ, południe, wschód, zachód, nie wolno z jednego sektora na drugi próbować przedostać się po skosie, bo grozi to niebezpieczeństwem. Należy tak zaplanować przemarsz, aby droga z A do B, zawierała jak najmniej zaminowanych sektorów. Na mapie, zaminowane sektory oznaczone zostały znakiem x, pozostałe sektory, oznaczone znakiem kropki, są niezaminowane. Niezaminowane są także sektory A i B. Zanim zaczniesz planować trasę przemarszu, musisz najpierw policzyć, jaka jest najmniejsza liczba zaminowanych sektorów, które trzeba będzie pokonać, aby dotrzeć z sektora A do sektora B.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę przypadków testowych. Każdy przypadek opisują w pierwszym wierszu dwie liczby całkowite a, b (2 ≤ a, b ≤ 1000) oznaczające wymiary prostokątnego pola walki. Każde takie pole opisane jest w a wierszach, w każdym po b znaków. Pliki wejściowe nie przekraczają 5MB.

Wyjście
Dla każdego przypadku testowego należy podać minimalną liczbę sektorów, jakie trzeba rozminować, aby dotrzeć z sektora A do sektora B.

Przykład

Wejście
1
5 7
..x.xx.
Axx.xx.
.xx.xB.
xx...xx
...x...

Wyjście
2