题目描述

Alice and Bob want to play a game. The game is played on a chessboard with $R$ rows and $C$ columns, for a total of $RC$ squares. Some of these squares are burned.

A king will be placed on an unburned square of the board, and Alice and Bob will make successive moves with the king.

In a move, the player must move the king to any of its 8 neighboring squares, with the following two conditions:

• The destination square must not be burned
• The king must never have been in the destination square before.

If a player can't make a move, he or she loses the game. Alice will move first; you need to determine who will win, assuming both players play optimally.

输入格式

The first line of input gives the number of cases, $N$.

$N$ test cases follow. The first line of each case will contain two integers, $R$ and $C$. The next $R$ lines will contain strings of length $C$, representing the $C$ squares of each row. Each string will contain only the characters '.', '#' and 'K':

• '#' means the square is burned;
• '.' means the square is unburned, and unoccupied; and
• 'K' means the king is in that cell at the beginning of the game.

There will be only one 'K' character in each test case.

输出格式

For each test case, output one line containing "Case #$X$: " (where $X$ is the case number, starting from 1) followed by A if Alice wins, or B if Bob wins.

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

Case #1: B
Case #2: A

提示

Limits

• $1 \leqslant N \leqslant 100$

Small dataset (7 Pts, Test set 1 - Visible)

• Time limit: 30 3 seconds.
• $1 \leqslant R, C \leqslant 4$

Large dataset (38 Pts, Test set 2 - Hidden)

• Time limit: 180 36 seconds.
• $1 \leqslant R, C \leqslant 15$