시티 게임

Bob은 전략 게임 프로그래밍 전문가이다. 그가 새로 만든 도시 건설 게임에서 도시는 여러 구역으로 이루어지며, 각 구역에는 도로, 나무, 공장, 건물이 있고 비어 있는 공간도 남아 있다. 목표는 이 빈 공간에 건물을 세워 최대한 많은 임대료를 버는 것이다. 건물은 반드시 직사각형이어야 하며, 가능한 한 크게 지어야 한다. 이미 있는 건물, 나무, 공장, 도로가 있는 칸 위에는 지을 수 없다.

각 구역은 같은 크기의 정사각형 단위 칸들로 이루어진 격자이다. 건물이 덮은 칸 하나마다 받는 임대료는 3$이다. 도시 전체는 $K$개의 구역으로 나뉘며, 각 구역은 고유의 길이 $M$과 너비 $N$을 가진다. 이미 사용 중인 칸은 R로, 빈 칸은 F로 표시한다.

각 구역마다 Bob이 세울 수 있는 가장 큰 직사각형 건물을 찾아, 그때 얻는 임대료를 구하시오.

첫 줄에 구역의 개수 $K$가 주어진다. 각 구역은 다음과 같이 주어진다. 첫 줄에 길이 $M$ ($M \le 1000$)과 너비 $N$ ($N \le 1000$)이 공백으로 구분되어 주어진다. 이어지는 $M$개의 줄에는 각각 $N$개의 기호가 공백 하나로 구분되어 주어진다.

• R — 사용 중인(예약된) 칸
• F — 빈 칸

각 구역 설명 뒤에는 구분을 위한 줄이 하나 있다.

각 구역마다, 그 구역에 세울 수 있는 가장 큰 직사각형 건물로 얻는 임대료(건물이 차지하는 칸 수에 $3$을 곱한 값)를 한 줄에 하나씩 출력한다.