FRAKTAL - konkurs programistyczny

Zawody

Jasiu i jego robot bierze udział w zawodach. Robot może poruszać się po prostokątnej mapie pól w metryce miasto. Startuje z lewego górnego pola do prawego dolnego i wraca z powrotem do punktu startu. Kiedy idzie na południowy-wschód może poruszać się tylko w prawo lub na dół, a w drodze powrotnej może poruszać się wyłącznie w lewo lub do góry. Robot powinien obrać taką drogę, aby odwiedzić jak najwięcej oznaczonych pól z gwiazdkami, przy czym robot nie może przechodzić przez pola oznaczone znakiem x. Po zbadaniu mapy, Jasiu zdaje sobie sprawę, że zadanie nie jest takie proste i trzeba robota odpowiednio zaprogramować. Dlatego uprzejmie prosi Ciebie o pomoc w napisaniu programu, który pozwoli robotowi optymalnie przejść mapę. Mając do dyspozycji mapę 2D, w której zaznaczone są pola z gwiazdkami oraz pola x, po których robot poruszać się nie może, wyznacz maksymalną liczbę pól z gwiazdkami, do których robot może dotrzeć. Pola z gwiazdkami odwiedzone dwa razy liczone są tylko raz.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych. W pierwszym wierszu każdego zestawu znajdują się dwie liczby całkowite a, b (2 ≤ a, b ≤ 100) oznaczające długość i szerokość mapy. W kolejnych wierszach opisana jest mapa złożona z b wierszy, każdy wiersz po a znaków o następujących oznaczeniach:
. - chodnik, po którym może poruszać się robot
* - pole z gwiazdką
x - pola, po których robot poruszać się nie może

Należy założyć, że lewe górne pole oraz prawe dolne to pole, w którym nie ma znaku x oraz, że istnieje co najmniej jedna droga łącząca lewe górne pole z polem prawym dolnym.

Wyjście
Na wyjściu, dla każdego przypadku testowego, należy wypisać maksymalną liczbę pól z gwiazdkami, które robot może odwiedzić.

Przykład

Wejście
2
8 6
*.......
....**x.
..**..x*
.*xxx*..
...x*.x*
*.......
5 5
.*...
.xxx.
*.*.*
.xxx.
.*.*.

Wyjście
7
5