땅 팔기

어떤 나라의 영토는 단위 정사각형들로 나뉘어 있으며, 각 칸은 잔디 또는 늪이다. 담당 관청은 직사각형이 아닌 모양을 처리하지 못하기 때문에, 땅은 격자에 맞춰진 직사각형 블록 단위로만 살 수 있다. 관청은 곱셈을 하지 못해 넓이 대신 둘레로 값을 매기므로, 한 블록의 가격은 그 블록의 둘레와 같다.

Per는 직사각형 모양의 땅 한 필지를 가지고 있으며, 이를 여러 개의 (서로 겹쳐도 되는) 조각으로 나누어 팔려고 한다. 직사각형 블록을 팔 때 관청은 그 블록의 남동쪽(오른쪽 아래) 모서리 좌표만 기록한다. 이미 같은 남동쪽 모서리를 가진 블록이 팔린 적이 있으면 관청은 그 거래를 거절한다. 그 외에는 블록이 서로 겹쳐도 되므로, Per는 서로 다른 남동쪽 모서리마다 블록을 하나씩 팔 수 있다. 늪 칸을 포함한 블록은 아무도 사지 않으므로, 파는 모든 블록은 전부 잔디로만 이루어져야 한다.

Per는 돈을 최대한 많이 벌기 위해, 가능한 각 남동쪽 모서리마다 그 모서리를 오른쪽 아래 꼭짓점으로 하면서 전부 잔디로 이루어진 직사각형 블록 중 둘레가 가장 큰 것을 판다. 예를 들어 가로 $2$, 세로 $4$인 블록의 둘레는 $2\times(2+4)=12$이다. 그가 파는 모든 블록에 대해, 각 둘레의 블록을 몇 개씩 파는지 구하여라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 한 줄에 두 정수 $n$과 $m$ ($1 \le n, m \le 1000$): Per가 가진 필지의 행 수와 열 수.
• 이어서 $n$개의 줄이 주어지며, 각 줄은 $m$개의 문자로 이루어진다. 각 문자는 #(늪) 또는 .(잔디)이다. $i$번째 행, $j$번째 열의 문자는 위치 $(i, j)$의 칸을 나타내며, 필지의 북서쪽 모서리는 $(1, 1)$, 남동쪽 모서리는 $(n, m)$이다.

각 테스트 케이스마다, 최적의 계획에서 각 둘레의 블록을 몇 개씩 파는지 나타내는 0개 이상의 줄을 출력한다. 둘레가 $i$인 블록을 $p_i$개 판다면, count x perimeter 형식으로 한 줄을 출력한다(개수, 공백, 문자 x, 공백, 그리고 둘레). 줄은 둘레 $i$가 증가하는 순서로 정렬하고, 같은 $i$를 가진 줄을 두 번 출력하지 않으며, $p_i = 0$인 둘레는 출력하지 않는다.