King (Small)

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.

At the start of the game a king stands on one unburned square. Alice and Bob then move the king in turn.

A move takes the king to one of its 8 neighbouring squares and has to satisfy two conditions:

• the destination square is not burned;
• the king has never stood on the destination square before.

A player who cannot move loses the game. 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 a test case contains two integers $R$ and $C$. Each of the next $R$ lines contains a string of length $C$ that describes the $C$ squares of one row. Each string uses only the characters '.', '#' and 'K':

• '#' means the square is burned;
• '.' means the square is unburned and empty;
• 'K' means the king stands on that square at the start of the game.

Each test case contains exactly one 'K'.

Limits

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

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