Land Swindle

(...) So, for instance, I was told that a certain resident of the capital, having received a three-room apartment with a kitchen on Zemlyanoy Val, without any fifth dimension there or other such contraptions that can leave your head spinning, turned it in the blink of an eye into a four-room apartment with a kitchen: he simply split one room in two with a partition. Then he traded that apartment for two separate ones in different districts of Moscow, one of three rooms and one of two. You will grant, surely, that this already makes five rooms. The three-room one he traded for two separate two-room apartments with kitchens, and so became the owner, as you can see for yourself, of six rooms, scattered chaotically all over Moscow, it is true. He was just about to bring off his last and most dazzling stroke, having run an advertisement in the paper that he wished to trade six rooms in various parts of Moscow for one five-room apartment on Zemlyanoy Val, when his enterprise came to a halt for reasons entirely beyond his control. Perhaps he still occupies some room even now, but I can assure you it is not in Moscow. There, that is what you call a man with his head screwed on right, and here you are telling me about the fifth dimension!

Mikhail Bulgakov, "The Master and Margarita"

Byteasar is the proud owner of a rectangular plot of land which, for surveying purposes, he has divided into $m \times n$ unit squares. As it happens, every square is either a meadow or a swamp. Byteasar would like to sell his plot and set off for the Caribbean. Since he has no plans to return to Byteotia any time soon, nothing stops him from selling it to many buyers at once.

Each buyer may purchase some rectangular piece of the plot, its sides running along the sides of the unit squares. Unfortunately, nobody will tolerate a swamp anywhere inside their piece, so every piece must consist of meadow squares only. Pieces sold to different people may overlap, but no two of them may share the same bottom-right corner (the Byteotian clerks, though hardly renowned for their sharpness, would surely notice that). The price of a piece, as Byteotian law decrees, is proportional to its perimeter. What, then, is the most Byteasar can earn? (The bottom-right corner of a piece is its meadow square with the largest row index and the largest column index.)

The first line of standard input contains the number of test cases $T$. Then follow $T$ test cases, each in the following form. The first line of a test case contains two integers $n$ and $m$ ($1 \le n, m \le 2000$), the height and the width of the plot. The next $n$ lines each contain $m$ characters: the $j$-th character of the $i$-th line is . if the square at coordinates $(i, j)$ is a meadow, or # if it is a swamp.

For each test case, print a single integer on its own line: the maximum total perimeter of the pieces that Byteasar can sell.