PortalTM 是由 Valve Software 开发并发行的一款第一人称解谜/平台游戏。游戏的核心理念是在墙壁上创建两个传送门，然后穿过一个传送门并从另一个传送门出来。本题采用了类似的构思，但并不要求你玩过 Portal。
对于本题，你身处一个 $R \times C$ 的网格中。此外，网格中的某个位置还有一个美味的蛋糕。你非常饥饿，希望以最少的移动步数到达蛋糕处。你可以向北、南、东或西移动到相邻的空单元格。此外，你还有能力在墙壁上创建传送门。
为了帮助你到达蛋糕处，你拥有一把传送门枪，可以发射两种类型的传送门：黄色传送门和蓝色传送门。通过向北、南、东或西发射传送门枪即可创建传送门。这会发射一个能量球，并在其击中的第一面墙壁上创建一个传送门。注意，在本题中，发射传送门枪不计入移动步数。如果你向蛋糕发射传送门枪，能量球会直接穿过它。
在创建了黄色传送门和蓝色传送门后，你可以穿过黄色传送门到达蓝色传送门，反之亦然。利用这些传送门，你或许能更快地到达蛋糕处！只有在同时创建了黄色和蓝色传送门后，你才能使用它们。
考虑以下网格：
灰色单元格代表墙壁，白色单元格代表空单元格，红色圆圈表示你的位置。
假设你向东发射一个蓝色传送门。传送门会在它击中的第一面墙壁上创建，结果如下：
现在假设你向南发射一个黄色传送门：
接下来你向南移动一步：
现在是有趣的部分。如果你再向南移动一步，你就会穿过黄色传送门到达蓝色传送门：
在任何时候，只能存在一个黄色传送门和一个蓝色传送门。例如，如果你尝试向西创建一个蓝色传送门，原有的蓝色传送门就会消失：
只有当发射了另一种同颜色的传送门时，原有的传送门才会消失。
注意，传送门是创建在墙壁的一侧的。如果一面墙的东侧有一个传送门，你必须从东侧进入这面墙才能穿过传送门。否则，你将撞向墙壁，这是不可能通过的。
最后，你不能将两个传送门放在同一个位置。如果你尝试向一面已经有传送门的墙壁侧面发射传送门，第二个传送门将无法形成。
给定迷宫、你的初始位置和蛋糕的位置，你需要找出到达蛋糕所需的最少移动步数（如果可能的话）。记住，发射传送门枪不计入移动步数。
输入格式
输入的第一行给出了测试用例的数量 $N$。接下来是 $N$ 个测试用例。
每个测试用例的第一行包含两个整数 $R$ 和 $C$，中间用空格隔开。接下来 $R$ 行，每行包含 $C$ 个字符，表示地图：
.表示空单元格；#表示墙壁；O表示你的起始位置；X表示蛋糕的位置。
每个测试用例中恰好包含一个 O 和一个 X 字符。
网格之外的区域均为墙壁，你可以利用它们来创建传送门。
输出格式
对于每个测试用例，输出一行 "Case #$X$: $Y$"，其中 $X$ 是测试用例的编号，$Y$ 是到达蛋糕所需的最少移动步数；如果无法到达蛋糕，则输出 "THE CAKE IS A LIE"。
数据范围
时间限制：5 秒。 内存限制：1GB。
小数据集（测试集 1 - 可见；10 分）
$N = 200$ $1 \le R, C \le 8$
大数据集（测试集 2 - 隐藏；15 分）
$N = 50$ $1 \le R, C \le 15$
样例
样例输入 1
3 4 7 .O..##. .#..... .#.#### .#...X. 5 5 O.... ..... ..... ..... ....X 1 3 O#X
样例输出 1
Case #1: 4 Case #2: 2 Case #3: THE CAKE IS A LIE
说明
以下是第一个样例的移动序列（注意发射传送门枪不计入移动步数）：
- 向东移动一步。
- 向北发射一个蓝色传送门。
- 向南发射一个黄色传送门。
- 向北移动一步，穿过蓝色传送门。
- 向东发射一个蓝色传送门。
- 向南移动一步，穿过黄色传送门。
- 向西移动一步。
- 吃掉你美味且湿润的蛋糕。
PortalTM 是 Valve Inc. 的商标。Valve Inc. 不认可且未参与 Google Code Jam。