Description

Alice 和 Bob 想玩一个游戏。游戏在一个有 $R$ 行 $C$ 列的棋盘上进行，总共有 $RC$ 个格子。其中一些格子已经被烧毁。

一枚国王会被放置在棋盘上的某个未烧毁的格子上，Alice 和 Bob 轮流移动国王。

每次移动时，玩家必须将国王移动到其 8 个相邻格子中的任意一个，但需满足以下两个条件：

• 目标格子不能是烧毁的格子；
• 国王之前从未到过目标格子。

如果某个玩家无法移动，则该玩家输掉游戏。Alice 先手。假设双方都采取最优策略，请你判断谁会获胜。

Input Format

输入的第一行包含测试用例的数量 $N$。

接下来有 $N$ 组测试数据。每组测试数据的第一行包含两个整数 $R$ 和 $C$。接下来的 $R$ 行，每行是一个长度为 $C$ 的字符串，表示该行的 $C$ 个格子。每个字符串只包含字符 '.'、'#' 和 'K'：

• '#' 表示该格子已被烧毁；
• '.' 表示该格子未被烧毁且未被占据；
• 'K' 表示国王初始所在的格子。

每个测试用例中只会有一个 'K' 字符。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$X$: "（其中 $X$ 是测试用例编号，从 1 开始），后接 A（如果 Alice 获胜）或 B（如果 Bob 获胜）。

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

Case #1: B
Case #2: A

Hint

数据范围

• $1 \leqslant N \leqslant 100$

小数据范围（7 分，测试点 1 - 可见）

• 时间限制：30 3 秒。
• $1 \leqslant R, C \leqslant 4$

大数据范围（38 分，测试点 2 - 隐藏）

• 时间限制：180 36 秒。
• $1 \leqslant R, C \leqslant 15$

由 ChatGPT 4.1 翻译