如你所知，Absurdistan 国充满了各种怪异之事。例如，整个国家可以划分为单位正方形，每个正方形要么是草地，要么是沼泽。此外，这个国家因其无能的官僚而闻名。如果你想买一块土地（称为地块），你只能购买矩形区域，因为他们无法处理其他形状。地块的价格由他们决定，并且与地块的周长成正比，因为这些官僚不会做整数乘法，从而无法计算地块的面积。

Per 在 Absurdistan 拥有一块被沼泽包围的土地，他想把它卖给一些买家，可能会分块出售。当他出售自己土地的一个矩形部分时，他必须向当地的官僚申报。他们首先会告诉他这块地应该卖多少钱。然后，他们会记录下新业主的名字以及所售地块东南角的坐标。如果已经有人拥有一个东南角在相同位置的地块，官僚们就会拒绝办理所有权变更。

Per 意识到他可以轻易地钻这个系统的空子。他可以出售重叠的区域，因为官僚们只检查东南角是否相同。然而，没有人想购买包含沼泽的地块。

在这个例子中，深色方块代表沼泽。例如，Per 可以出售三个重叠的灰色区域，尺寸分别为 $2 \times 1$、$2 \times 4$ 和 $4 \times 1$。总周长为 $6 + 12 + 10 = 28$。注意，他可以通过出售更多的土地来获得更多的钱。该图对应于样例输入中的情况。

现在 Per 想知道，为了最大化他的利润，他需要出售多少个各种周长的地块。你能帮他吗？你可以假设，只要地块不包含任何沼泽，他总能为每块土地找到买家。此外，Per 确信他的地块内没有任何一个方块已被其他人拥有。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100。之后对于每个测试用例：

• 一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 1\,000$）：Per 的土地的尺寸。
• $n$ 行，每行包含 $m$ 个字符。每个字符要么是 #，要么是 .。如果位置 $(i, j)$ 是沼泽，则第 $i$ 行的第 $j$ 个字符为 #；如果是草地，则为 .。Per 的土地的西北角坐标为 $(1, 1)$，东南角坐标为 $(n, m)$。

输出格式

对于每个测试用例：

• 输出零行或多行，包含为了最大化利润，Per 需要出售的每种周长的地块数量的完整列表。具体来说，如果在最优解中 Per 应该出售 $p_i$ 个周长为 $i$ 的地块，则输出单行 pi x i。这些行应按 $i$ 的递增顺序排序。任意两行不应具有相同的 $i$ 值，并且不应输出 $p_i = 0$ 的行。

样例

输入格式 1

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

输出格式 1

6 x 4
5 x 6
5 x 8
3 x 10
1 x 12