시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB75480.000%

문제

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.

Limits

• 1 ≤ N ≤ 100
• 1 ≤ RC ≤ 4

출력

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.

예제 입력 1

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


예제 출력 1

Case #1: B
Case #2: A


채점 및 기타 정보

• 예제는 채점하지 않는다.