집 지을 땅 (작은 입력)

면접 대비

시간 제한5초메모리 제한512 MB

요약

각 격자 지도에서 잔디와 관목 칸만으로 이루어진 가장 큰 직사각형의 넓이를 구합니다.

난이도: 보통10점 중 5점
유형: 스택, 행렬
정답자: 아직 제출이 없습니다

문제

땅을 사서 가장 넓은 직사각형 밭을 만들려고 한다. 땅을 측량해 보니 장애물이 여기저기 있어서 지도를 그렸다. 지도의 각 칸에는 그 칸의 상태를 잔디(G), 바위(R), 물(W), 덤불(S), 나무(T) 중 하나로 적었다. 잔디는 깎을 수 있고 덤불은 파낼 수 있지만, 물과 바위와 나무는 치울 수 없다.

지도가 주어질 때, 치울 수 있는 칸으로만 이루어진 가장 넓은 직사각형의 넓이를 구하라. 직사각형의 변은 지도의 격자와 나란해야 한다.

입력

첫 줄에 테스트 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 땅의 길이 L과 너비 W가 공백으로 구분되어 주어진다.
이어서 W개의 줄이 주어지고, 각 줄에는 문자 L개가 붙어서 주어진다. 각 문자는 그 칸의 상태를 나타내며 G, R, W, S, T 중 하나이다.

제한

$1 \le L \le 50$
$1 \le W \le 50$
$1 \le N \le 10$

출력

각 테스트 케이스마다 Case #x: 뒤에 만들 수 있는 가장 넓은 직사각형의 넓이를 한 줄에 출력한다. $x$ 는 테스트 케이스 번호이며 1부터 센다. 치울 수 있는 칸이 하나도 없으면 0을 출력한다.

예제3

예제 1

입력

4
1 1
G
2 2
GS
SG
2 2
GT
GG
5 8
GGTGG
TGGGG
GSSGT
GGGGT
GWGGG
RGTRT
RTGWT
WTWGR

예상 출력

Case #1: 1
Case #2: 4
Case #3: 2
Case #4: 9

예제 2
입력
```
1
3 3
RWT
TRW
WTR
```
예상 출력
```
Case #1: 0
```
예제 3
입력
```
2
1 1
T
1 1
S
```
예상 출력
```
Case #1: 0
Case #2: 1
```