그리드셉션

전설의 도둑 Jom Codd는 다른 사람의 꿈에 침입할 수 있다. 꿈을 들여다보는 기술이 아직 그리 좋지 않아서, Codd는 꿈을 흰색 또는 검은색 단위 칸으로 이루어진 꿈 격자로 본다.

시작 꿈 격자가 주어지면, Codd는 더 깊이 들어갈 수 있다. 흰 칸은 흰 칸으로 이루어진 2x2 격자로, 검은 칸은 검은 칸으로 이루어진 2x2 격자로 바꾼다. 그러면 가로세로가 각각 두 배, 넓이가 네 배인 새 꿈 격자가 만들어진다. Codd는 그 격자에서 다시 더 깊이 들어갈 수 있으며, 이를 계속 반복할 수 있다. 예를 들어 다음과 같은 시작 꿈 격자가 주어졌다고 하자:

BBB
BWB
BBB

한 번 더 깊이 들어가면 다음과 같은 새 꿈 격자가 나온다:

BBBBBB
BBBBBB
BBWWBB
BBWWBB
BBBBBB
BBBBBB

거기서 한 번 더 깊이 들어가면 다음 격자가 나온다:

BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB

이후도 같은 방식으로 계속된다.

Codd는 방금 어떤 꿈에 침입해 시작 꿈 격자를 살펴보았다. 매우 어려운 임무 중이며 여러 번 더 깊이 들어가야 한다는 것을 알고 있다. 길을 찾기 위해 시작 꿈 격자에 있는 여러 패턴을 살펴본다. 패턴은 변을 공유하며 연결된 칸들의 단일 집합과 그 칸들의 색으로 이루어진다. 꼭짓점만 맞닿은 경우는 연결로 보지 않는다. 패턴 안에는 빈 칸이 있을 수 있지만, 패턴의 칸들이 하나의 연결된 집합을 이루어야 한다. 이런 빈 칸은 패턴에 포함되지 않는다. 두 패턴은 칸의 수와 배치(회전하거나 뒤집지 않은 상태)가 같고 색도 같을 때에만 같은 패턴이다.

예를 들어 시작 격자에는 다음과 같은 8칸 패턴이 있다:

BBB
B B
BBB

이 패턴은 한 번 깊이 들어간 격자에는 없지만, 두 번, 세 번, 그 이상 깊이 들어간 모든 격자에는 있다.

Codd가 찾는 것은 시작 꿈 격자에 있으면서, 더 깊은 꿈 격자 중 적어도 구골($10^{100}$)개 이상에 나타나는 가장 큰 패턴이다. 위 예시에서는 앞의 패턴이 그런 가장 큰 패턴이다. 한 번 깊이 들어간 격자에는 없지만, 더 깊은 격자 중 구골 개 이상에는 나타난다. 크기가 더 작은 다른 패턴도 이 조건을 만족하지만, 9칸짜리 패턴 중에서는 만족하는 것이 없다. 그런 패턴이 있다면 시작 꿈 격자 전체와 똑같아야 하는데, 그런 패턴은 어떤 더 깊은 꿈 격자에도 나타나지 않으므로 구골 개의 격자에 나타날 수 없다.

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 나온다. 각 테스트 케이스는 꿈 격자의 행 수 R과 열 수 C를 나타내는 두 정수로 시작한다. 그 뒤로 각각 C글자로 이루어진 R개의 줄이 이어진다. 각 글자는 B 또는 W이다. 이 줄들이 꿈 격자를 그대로 나타낸다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 Codd의 조건을 만족하는 패턴 가운데 하나의 가능한 최대 크기이다.

1 <= T <= 100.

Sample Case #1은 문제에서 설명한 격자이다.

Sample Case #2에서 가능한 최대 패턴 중 하나는 다음과 같다:

BBB
WB

크기가 같은 다른 최대 패턴은 다음과 같다:

BBB
W W

Sample Case #3에서는 시작 꿈 격자 전체가 최대 패턴이다.

Sample Case #4에서 W 다섯 개는 서로 연결되어 있지 않아 유효한 패턴이 되지 못한다. 대신 다음 패턴이 최대 패턴이다:

WB
BW

Sample Case #5에서는 시작 꿈 격자 전체가 최대 패턴이다. 이 격자는 BW에서 깊이 들어간 결과와 같지만, Codd는 얕은 단계로 돌아가지 않으므로 이는 중요하지 않다.