King Game

Alice and Bob play a game on a chessboard with $R$ rows and $C$ columns, so $RC$ squares in total. Some of the squares are burned.

A king is placed on an unburned square, and Alice and Bob move it one step at a time, taking turns.

On a turn the player must move the king to one of the 8 squares next to its current square, subject to two conditions:

• the destination square must not be burned;
• the king must never have entered that square before. The starting square already counts as entered.

A player who cannot move the king on their turn loses. Alice moves first. Determine who wins when both players play optimally.

The first line contains the number of test cases, $N$.

$N$ test cases follow. The first line of each case contains two integers $R$ and $C$. The next $R$ lines each contain a string of length $C$ that describes the $C$ squares of one row. Each string uses only the characters ., # and K.

• # is a burned square.
• . is a square that is unburned and unoccupied.
• K is the square the king starts on. That square is unburned.

Each test case contains exactly one K.

For each test case, print one line: Case #X: followed by A if Alice wins or B if Bob wins. Here $X$ is the case number, starting from 1.

• $1 \le N \le 100$
• $1 \le R, C \le 15$