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

国王将被放置在棋盘上一个未烧毁的方格中，Alice 和 Bob 将轮流移动国王。

在一次移动中，玩家必须将国王移动到其周围 8 个相邻方格中的任意一个，并满足以下两个条件：

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

如果一名玩家无法进行移动，则该玩家输掉游戏。Alice 先手；假设双方都采取最优策略，你需要确定谁会获胜。

输入格式

输入的第一行包含测试用例的数量 $N$。接下来是 $N$ 个测试用例。每个测试用例的第一行包含两个整数 $R$ 和 $C$。接下来的 $R$ 行包含长度为 $C$ 的字符串，表示每一行的 $C$ 个方格。每个字符串仅包含字符 '.'、'#' 和 'K'：

• '#' 表示该方格已烧毁；
• '.' 表示该方格未烧毁且未被占用；
• 'K' 表示游戏开始时国王位于该方格。

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

输出格式

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

样例

输入格式 1

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

输出格式 1

Case #1: B
Case #2: A