그리드셉션

대도둑 Jom Codd는 다른 사람의 꿈에 침투할 수 있다. 아직 꿈을 보는 기술이 그다지 좋지 않기 때문에, Codd에게 꿈은 단위 칸으로 이루어진 꿈 격자로 보이며, 각 칸은 흰색 또는 검은색이다.

시작 꿈 격자가 주어지면, Codd는 각 흰색 칸을 흰색 칸으로 이루어진 2x2 격자로 바꾸고 각 검은색 칸을 검은색 칸으로 이루어진 2x2 격자로 바꾸어 더 깊이 들어갈 수 있다. 그러면 네 배 더 큰 새로운 꿈 격자가 만들어진다. 그는 그 격자에서 다시 더 깊이 들어갈 수 있으며, 이를 계속할 수 있다. 예를 들어, 다음 시작 꿈 격자가 주어졌다고 하자.

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칸 패턴은 없다. 그러한 유일한 패턴은 시작 꿈 격자 전체와 동일해야 하는데, 그 패턴은 어떤 더 깊은 꿈 격자에도 절대 나타나지 않으며, 구골개의 격자에 나타나는 것은 더더욱 불가능하다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

1 ≤ R ≤ 3. 1 ≤ C ≤ 4.

테스트 세트 2 (비공개)

1 ≤ R ≤ 20. 1 ≤ C ≤ 20.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 R과 C가 있는 한 줄로 시작하며, 이는 각각 꿈 격자의 행 수와 열 수이다. 이어서 각 테스트 케이스마다 C개의 문자로 이루어진 R개의 줄이 더 주어진다. 각 문자는 B 또는 W이다. 이 줄들은 꿈 격자를 그대로 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 위에서 설명한 Codd의 요구 사항을 만족하는 적어도 하나의 패턴이 가질 수 있는 가장 큰 크기이다.

예제 케이스 #1은 문제 설명에서 다룬 경우이다.

예제 케이스 #2에서 가능한 가장 큰 패턴 중 하나는 다음과 같다.

BBB WB

크기가 같은 또 다른 패턴은 다음과 같다.

BBB W W

예제 케이스 #3에서는 시작 꿈 격자 전체가 가장 큰 패턴이다.

예제 케이스 #4에서 다섯 개의 W는 연결되어 있지 않으므로 유효한 패턴을 이루지 못한다는 점에 유의하라. 하지만 다음은 가장 큰 패턴이다.

WB BW

예제 케이스 #5에서는 시작 꿈 격자 전체가 가장 큰 패턴이다. 이 격자가 우연히 BW에서 시작해 더 깊이 들어갔을 때 Codd가 얻게 되는 격자와 같더라도, 이는 관계없다는 점에 유의하라. Codd는 절대로 "더 얕은 곳으로 가지" 않기 때문이다.