Selling Land

The country of Absurdistan is divided into unit squares, each of which is either grass or swamp. Land can only be bought as a rectangular block whose sides are aligned with the grid, because the local bureaucrats cannot handle any other shape. The price of a block equals its perimeter: the bureaucrats cannot multiply, so they charge for the perimeter rather than the area.

Per owns one rectangular parcel and wants to sell it off, possibly in many overlapping pieces. Whenever he sells a rectangular block, the bureaucrats record only the coordinates of its south-east (bottom-right) corner. They refuse a sale if a block with the same south-east corner has already been sold. Otherwise overlapping blocks are allowed, so Per may sell one block for every distinct south-east corner. No buyer will accept a block that contains any swamp square, so every block he sells must consist entirely of grass.

To make as much money as possible, for each possible south-east corner Per sells the all-grass rectangular block that has that corner and the largest possible perimeter. For example, a block that is $2$ wide and $4$ tall has perimeter $2\times(2+4)=12$. Over all the blocks he sells, determine how many blocks he sells of each perimeter.

The first line contains an integer $T$ ($1 \le T \le 100$), the number of test cases. Each test case is given as follows:

• One line with two integers $n$ and $m$ ($1 \le n, m \le 1000$): the number of rows and columns of Per's parcel.
• $n$ lines follow, each containing $m$ characters. Each character is either # (swamp) or . (grass). The character in row $i$, column $j$ describes the square at position $(i, j)$; the north-west corner of the parcel is $(1, 1)$ and the south-east corner is $(n, m)$.

For each test case, output zero or more lines describing how many blocks of each perimeter Per sells in the optimal plan. If he sells $p_i$ blocks of perimeter $i$, print one line of the form count x perimeter (the count, a space, the letter x, a space, then the perimeter). Sort the lines by increasing perimeter $i$, print no two lines with the same $i$, and omit any perimeter for which $p_i = 0$.