Becca và Terry là hai nhà vi sinh vật học có một cuộc cạnh tranh thân thiện. Khi cần nghỉ ngơi sau công việc nghiên cứu, họ chơi một trò chơi trên ma trận gồm các ô đơn vị, có \(R\) hàng và \(C\) cột. Ban đầu, mỗi ô hoặc trống, hoặc chứa chất phóng xạ.

Ở lượt của một người chơi, nếu ma trận không còn ô trống thì người đó thua. Nếu vẫn còn, họ chọn một ô trống và đặt vào đó một khuẩn lạc. Có hai loại khuẩn lạc: H (ngang) và V (dọc).

• Khi đặt khuẩn lạc H vào một ô trống, nó chiếm ô ấy (khiến ô không còn trống), rồi cố lan sang ô ngay phía tây (nếu có) và ô ngay phía đông (nếu có).
• Khi đặt khuẩn lạc V vào một ô trống, nó chiếm ô ấy, rồi cố lan sang ô ngay phía nam (nếu có) và ô ngay phía bắc (nếu có).

Mỗi khi khuẩn lạc thuộc bất kỳ loại nào cố lan vào một ô:

• Nếu ô chứa chất phóng xạ, khuẩn lạc bị đột biến và người vừa đặt nó thua cuộc.
• Nếu ô trống, khuẩn lạc chiếm ô đó, rồi quy tắc trên lại được kích hoạt, tức là nó tiếp tục cố lan xa hơn.
• Nếu ô đã chứa vi khuẩn thuộc bất kỳ loại nào, khuẩn lạc không lan vào ô đó.

Có thể mọi nước đi hiện có của một người chơi đều khiến họ thua, nên họ chắc chắn thất bại. Các phần giải thích ví dụ bên dưới minh họa cách trò chơi diễn ra.

Becca đi trước, sau đó hai người luân phiên cho đến khi một người thua. Nếu cả hai chơi tối ưu, ai sẽ thắng? Nếu Becca thắng, cô có bao nhiêu nước mở đầu thắng khác nhau? Hai nước mở đầu khác nhau khi và chỉ khi chúng dùng ô khác nhau, loại khuẩn lạc khác nhau, hoặc cả hai.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(R\) và \(C\), lần lượt là số hàng và số cột của ma trận. Tiếp theo là \(R\) dòng, mỗi dòng gồm \(C\) ký tự. Ký tự thứ \(j\) trên dòng thứ \(i\) biểu diễn ô ở hàng \(i\), cột \(j\). Mỗi ký tự là . (ô trống) hoặc # (ô chứa chất phóng xạ).

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à số nguyên: bằng 0 nếu Becca không thắng; nếu Becca thắng, đó là số nước mở đầu thắng khác nhau mà cô có thể thực hiện 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 4\), \(1 \le C \le 4\).
• Test Set 2 (ẩn): \(1 \le R \le 15\), \(1 \le C \le 15\).

Đ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
2 2
..
.#
4 4
.#..
..#.
#...
...#
3 4
#.##
....
#.##
1 1
.
1 2
##

Case #1: 0
Case #2: 0
Case #3: 7
Case #4: 2
Case #5: 0

Nguồn

Google Code Jam 2019, Vòng 1C, bài Bacterial Tactics.

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