Siêu trộm Jom Codd có khả năng thâm nhập vào giấc mơ của người khác. Vì công nghệ quan sát giấc mơ vẫn chưa tốt lắm, Codd nhìn thấy một giấc mơ dưới dạng một lưới giấc mơ gồm các ô đơn vị, mỗi ô có màu trắng hoặc đen.

Từ một lưới giấc mơ ban đầu, Codd có thể đi sâu hơn bằng cách thay mỗi ô trắng bằng một lưới \(2\times2\) toàn ô trắng và mỗi ô đen bằng một lưới \(2\times2\) toàn ô đen; thao tác này tạo ra một lưới giấc mơ lớn gấp bốn lần. Anh có thể tiếp tục đi sâu hơn từ lưới mới ấy, rồi lặp lại như vậy. Chẳng hạn, với lưới giấc mơ ban đầu:

BBB
BWB
BBB

đi sâu hơn một lần tạo ra lưới mới:

BBBBBB
BBBBBB
BBWWBB
BBWWBB
BBBBBB
BBBBBB

và đi sâu hơn một lần nữa tạo ra:

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

và cứ tiếp tục như vậy.

Codd vừa thâm nhập vào một giấc mơ và quan sát lưới giấc mơ ban đầu của nó. Anh đang thực hiện một nhiệm vụ rất khó và biết rằng mình sẽ phải đi sâu hơn rất nhiều lần. Để hỗ trợ việc định hướng, anh xem xét nhiều mẫu khác nhau trong lưới ban đầu. Một mẫu gồm một nhóm ô duy nhất liên thông qua cạnh chung (chỉ chung góc không được tính là liên thông), cùng với màu của các ô đó. Mẫu có thể có các khoảng trống bên trong, miễn là các ô của mẫu tạo thành một nhóm liên thông duy nhất; những khoảng trống ấy không được coi là một phần của mẫu. Hai mẫu giống nhau khi và chỉ khi chúng có cùng số lượng và cách sắp xếp các ô (không lật đối xứng hay xoay), với các màu tương ứng giống nhau.

Ví dụ, trong các lưới trên, mẫu 8 ô sau xuất hiện trong lưới ban đầu:

BBB
B B
BBB

Nó không xuất hiện sau khi đi sâu hơn một lần, nhưng xuất hiện sau khi đi sâu hơn hai lần, ba lần, và cứ như vậy trong mọi lưới giấc mơ sâu hơn nữa.

Codd muốn tìm mẫu lớn nhất từ lưới giấc mơ ban đầu mà sẽ xuất hiện trong ít nhất một googol (\(10^{100}\)) lưới giấc mơ sâu hơn. Với ví dụ đã cho, mẫu trên là mẫu lớn nhất như vậy. Mặc dù nó không xuất hiện sau lần đi sâu đầu tiên, nó vẫn xuất hiện ở ít nhất một googol mức sâu hơn. Những mẫu khác có kích thước nhỏ hơn cũng thỏa điều kiện, nhưng không có mẫu 9 ô nào thỏa; mẫu 9 ô duy nhất có thể có phải giống hệt toàn bộ lưới ban đầu, và mẫu đó sẽ không bao giờ xuất hiện trong bất kỳ lưới sâu hơn nào, chứ chưa nói đến một googol lưới.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa hai số nguyên \(R\) và \(C\): lần lượt là số hàng và số cột của lưới giấc mơ. Tiếp theo là \(R\) dòng, mỗi dòng gồm \(C\) ký tự; mỗi ký tự là B hoặc W. Các dòng này biểu diễn trực tiếp lưới giấc mơ.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là kích thước lớn nhất có thể của ít nhất một mẫu thỏa yêu cầu của Codd như mô tả ở trên.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

Test Set 1 (Hiển thị):

• \(1 \le R \le 3\).
• \(1 \le C \le 4\).

Test Set 2 (Ẩn):

• \(1 \le R \le 20\).
• \(1 \le C \le 20\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
3 3
BBB
BWB
BBB
2 3
BBB
WBW
1 1
W
3 3
WBW
BWB
WBW
2 4
BBWW
BBWW

Case #1: 8
Case #2: 5
Case #3: 1
Case #4: 4
Case #5: 8

BBB
WB

BBB
W W

WB
BW

Nguồn

Google Code Jam 2018, Vòng 2, bài Gridception.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.