Gruntowny przekręt

Limit pamięci: 64 MB

(...) Tak więc opowiadano mi na przykład, że pewien mieszkaniec stolicy, otrzymawszy trzy pokoje z kuchnią na Ziemlanym Wale, bez żadnego tam piątego wymiaru i innych takich rzeczy, od których można dostać kołowacizny, w mgnieniu oka przerobił je na cztery pokoje z kuchnią – jeden pokój przedzielił przepierzeniem na pół. Następnie zamienił to mieszkanie na dwa oddzielne mieszkania w różnych dzielnicach Moskwy, jedno trzy, a drugie dwupokojowe. Przyzna pani sama, że to już czyni pięć pokoi. Trzypokojowe zamienił na dwa oddzielne po dwa pokoje z kuchnią i stał się posiadaczem, jak sama pani to widzi, sześciu pokoi, co prawda rozrzuconych chaotycznie po całej Moskwie. Zamierzał właśnie wykonać ostatnią i najbardziej popisową woltę i zamieścił w gazecie ogłoszenie, że chce zamienić sześć pokoi w różnych punktach Moskwy na jedno pięciopokojowe mieszkanie na Ziemlanym Wale, kiedy jego działalność ustała z przyczyn całkowicie od niego niezależnych. Być może, że zajmuje i teraz jakiś pokój, mogę panią jednak zapewnić, że nie w Moskwie. Proszę, to się nazywa człowiek z głową na karku, a pani tu opowiada o piątym wymiarze!

— Michaił Bułhakow, „Mistrz i Małgorzata”

Bajtazar jest szczęśliwym właścicielem prostokątnej działki, którą dla celów geodezyjnych podzielił na kwadratów jednostkowych. Tak się złożyło, że każdy kwadrat jest albo łąką, albo bagnem. Bajtazar chciałby sprzedać swoją działkę i wyjechać na Karaiby. Ponieważ nie planuje w najbliższym czasie powrotu do Bajtocji, nic nie stoi na przeszkodzie, aby sprzedać ją wielu nabywcom jednocześnie...

Każdy nabywca może kupić pewien prostokątny kawałek działki o bokach pokrywających się z bokami jednostkowych kwadratów. Niestety, nikt nie zaakceptuje obecności w swoim kawałku bagna. Kawałki sprzedane różnym osobom mogą się nakładać, ale żadne dwa nie mogą mieć tego samego prawego dolnego rogu (bajtoccy urzędnicy, choć z lotności nie słyną, to zauważyliby z pewnością). Koszt działki, jak stanowi bajtockie prawo, jest proporcjonalny do jej obwodu. Ile zatem może najwięcej zarobić Bajtazar?

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba testów . Dalej następuje testów, w następującej postaci: Pierwszy wiersz testu zawiera dwie liczby całkowite i () oznaczające wysokość i szerokość działki. Dalej następuje wierszy, z których każda zawiera znaków. Znakiem -tym w -tym wierszu jest „.”, jeśli pole o współrzędnych jest łąką, lub „#”, jeśli jest bagnem.

Wyjście

Twój program powinien wypisać na standardowe wyjście, dla każdego zestawu, jedną liczbę całkowitą — maksymalną sumę obwodów działek, które może sprzedać Bajtazar.

Przykład

Dla danych wejściowych:

2
4 3
.##
#..
.#.
...
4 5
#.#.#
.....
..#..
.#...

poprawną odpowiedzią jest:

44
110