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