Selling Land

荒诞国由若干单位正方形组成，每个正方形要么是草地，要么是沼泽。由于当地官员无法处理复杂形状，土地只能以矩形地块的形式出售。地块的售价与其周长成正比，因为官员不会计算面积。

Per 拥有一片由沼泽环绕的土地，并希望将其中的草地出售。他可以将土地分成若干部分出售，也可以出售彼此重叠的矩形区域，但任何售出的矩形都不能包含沼泽。

每次出售土地时，官员只会记录新所有者的名字以及所售矩形东南角的坐标。如果已经有一块售出土地的东南角位于同一位置，官员就会拒绝这次交易。因此，对于每个位置，Per 至多能出售一块以该位置为东南角的矩形。

为了使总收益最大，对于每个可以作为东南角的位置，Per 都会选择一个不包含沼泽且周长最大的矩形出售。你的任务是统计最优方案中各种周长的矩形分别有多少个。

输入格式

第一行输入一个正整数，表示测试用例的数量。

对于每个测试用例：

第一行输入两个整数 $n$ 和 $m$ ，表示 Per 的土地共有 $n$ 行、 $m$ 列。

接下来 $n$ 行，每行包含 $m$ 个字符。字符 # 表示沼泽，字符 . 表示草地。

土地西北角的坐标为 $(1,1)$ ，东南角的坐标为 $(n,m)$ 。

对于每个测试用例，输出若干行，完整列出最优方案中各种周长的地块数量。

如果最优方案中需要出售 $p_i$ 块周长为 $i$ 的土地，则输出一行，依次包含 $p_i$ 、字符 x 和 $i$ ，三者之间各由一个空格分隔。

各行应按照周长 $i$ 从小到大的顺序输出。相同的周长只能输出一次，不要输出满足 $p_i=0$ 的行。

1
6 5
..#.#
.#...
#..##
...#.
#....
#..#.

样例输出表示，最优方案中需要出售 $6$ 块周长为 $4$ 的土地、 $5$ 块周长为 $6$ 的土地、 $5$ 块周长为 $8$ 的土地、 $3$ 块周长为 $10$ 的土地，以及 $1$ 块周长为 $12$ 的土地。

本题题面与测试数据整理自 BZOJ。

1
6 5
..#.#
.#...
#..##
...#.
#....
#..#.