eolymp
bolt
Try our new interface for solving problems

King

Time limit 1 second
Memory limit 64 MiB

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 R×C 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.

Input data

The first line of input gives the number of cases, N (1N100).

N test cases follow. The first line of each case will contain two integers, R and C (1R, C15). 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 exactly one 'K' character in each test case.

Output data

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.

Examples

Input example #1
2
2 2
K.
.#
4 2
K#
.#
.#
.#
Output example #1
Case #1: B
Case #2: A