To-Pong

Treść

Gobi to półpustynna i pustynna kraina obejmująca swym zasięgiem północne Chiny i południową Mongolię. Wśród naukowców znana jest przede wszystkim z doskonale zachowanych skamieniałości dinozaurów i ssaków kopalnych. Mało kto jednak pamięta, iż rejon ten był ważną częścią jedwabnego szlaku. To właśnie tędy przewożono cenne towary z Chin przez Persję, tereny Mezopotamii do krajów basenu Morza Śródziemnego.

Docent Doświadczalski wraz z międzynarodową grupą archeologów prowadzą prace wykopaliskowe na terenie jednego z byłych miast leżących na starożytnym szlaku. Wśród licznych znalezisk jedno szczególnie intryguje docenta. Jest to planszowa gra To-Pong. Dzięki dobrze zachowanym, bogato zdobionym opisom, naukowcowi udało się odtworzyć jej zasady.

Do przeprowadzenia gry potrzebna jest plansza podzielona na przylegające do siebie kwadraty (taka jak szachownica z tym, że wszystkie pola są tego samego koloru) oraz pionki. Pierwszy z graczy, zwany mistrzem, układa pionki na planszy. Zadaniem drugiego uczestnika – ucznia jest zdjęcie jak największej liczby pionków. Zdejmowanie można rozpocząć od dowolnie wybranego pionka. Kolejny zdejmowany pionek musi być sąsiadem (z lewej, prawej, dołu lub góry) poprzedniego, itd. Gra kończy się, gdy z planszy nie da się, zgodnie z zasadami, zdjąć kolejnego pionka.

Wśród wykopalisk docent Doświadczalski znalazł wiele gotowych układów początkowych To-Pong, używanych zapewne podczas nauki gry. Ze względu na to, iż naukowiec nie ma czasu na dokładne zapoznanie się z nimi, poprosił Ciebie o zbadanie układów i znalezienie optymalnych rozwiązań. Napisz program, który wykona to zadanie.

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

Pierwszy wiersz zestawu danych zawiera dwie liczby całkowite n i m (1<=n,m<=100) oddzielone pojedynczą spacja, oznaczające odpowiednio liczbę wierszy i kolumn planszy do gry. W kolejnych n wierszach podane jest początkowe ustawienie pionków na planszy. Każdy z tych wierszy zawiera po m znaków, przy czym . (kropka) reprezentuje pole puste, a litera o – pionek. Na planszy znajduje się co najmniej jeden i co najwyżej czterdzieści pionków.

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 jest maksymalna liczba pionków, jaką można zdjąć posługując się regułami To-Pong.

Przykład

dane wejściowe:
1
4 7
..o....
.ooo...
..o.o..
....o..

wynik:
3