Alice và Bob muốn chơi một trò chơi. Trò chơi được chơi trên một bàn cờ có \(R\) hàng và \(C\) cột, tổng cộng có \(RC\) ô vuông. Một số ô vuông trong số này đã bị cháy.

Một quân vua sẽ được đặt trên một ô chưa bị cháy của bàn cờ, và Alice cùng Bob sẽ lần lượt thực hiện các nước đi với quân vua đó.

Trong một nước đi, người chơi phải di chuyển quân vua đến bất kỳ ô nào trong số 8 ô lân cận của nó, với hai điều kiện sau:

• Ô đích phải không bị cháy.
• Quân vua chưa từng ở ô đích đó trước đây.

Nếu một người chơi không thể thực hiện nước đi, người đó sẽ thua cuộc. Alice sẽ đi trước; bạn cần xác định ai sẽ thắng, giả sử cả hai người chơi đều chơi tối ưu.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(N\).

\(N\) bộ test tiếp theo. Dòng đầu tiên của mỗi bộ test chứa hai số nguyên \(R\) và \(C\). \(R\) dòng tiếp theo sẽ chứa các chuỗi có độ dài \(C\), đại diện cho \(C\) ô của mỗi hàng. Mỗi chuỗi sẽ chỉ chứa các ký tự '.', '#' và 'K':

• '#' nghĩa là ô bị cháy;
• '.' nghĩa là ô chưa bị cháy và đang trống;
• 'K' nghĩa là quân vua đang ở ô đó khi bắt đầu trò chơi.

Sẽ chỉ có duy nhất một ký tự 'K' trong mỗi bộ test.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #\(X\): " (trong đó \(X\) là số thứ tự bộ test, bắt đầu từ 1) theo sau là A nếu Alice thắng, hoặc B nếu Bob thắng.

Ràng buộc

• \(1 \le N \le 100\)

Phân nhóm

• Small dataset (Test set 1 - Visible):

  • \(1 \le R, C \le 4\)

  • Large dataset (Test set 2 - Hidden):

  • \(1 \le R, 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ụ

2
2 2
K.
.#
4 2
K#
.#
.#
.#

Case #1: B
Case #2: A

Nguồn

Google Code Jam 2008, Vòng bán kết châu Mỹ, bài King.

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