AlgoLiga 2018

Hodowla reniferów

Jasiu posiada działki, na których na wydzielonej części postanowił hodować renifery. Ogrodził więc działki według swojego planu, a teraz musi policzyć powierzchnię wydzielonej części działki, aby równomiernie rozmieścić zwierzęta. Pojedynczą działkę reprezentują na planie punkty kratowe (kropki), na których Jasiu znakiem "x" zaznaczył ogrodzenie wydzielonej w celu hodowli części działki. Ogrodzenie tworzy łamaną zamkniętą bez samoprzecięć, a każda część ogrodzenia sąsiaduje dokładnie z dwoma innymi częściami. Znąjąc plan, oblicz powierzchnię ogrodzonej części działki, czyli łączną liczbę punktów stanowiących ogrodzenie oraz punktów kratowych wewnątrz ogrodzenia.

Wejście
W pierwszym wierszu znajduje się liczba d działek Jasia (0<d<=10). Każdą działkę opisują w pierwszym wierszu dwie liczby całkowite m, n - długość i szerokość działki (2<m,n<=500) i dalej n wierszy każdy po m znaków - plan działki wg opisanej w treści zadania składni.

Wyjście
Dla każdej działki w osobnym wierszu należy wypisać powierzchnię wydzielonej przez Jasia części działki.

Przykład

Wejście
2
6 3
xxxxxx
x....x
xxxxxx
8 7
.xxx....
xx.x.xxx
x..xxx.x
xx.....x
.xx.xxxx
..xxx...
........

Wyjście
18
36