Sokoban 是一款著名的日本益智游戏。Sokoban 在日语中意为“仓库管理员”。在这个游戏中，你的目标是将箱子推到仓库中指定的地点。要推动一个箱子，箱子后方和前方的区域必须是空的。这是因为你在推动箱子时站在箱子后面，且一次只能推动一个箱子。你不能将箱子推到棋盘外，在推动箱子时你也不能站在棋盘外。

例如，在下图中：

箱子 1 可以向四个方向中的任意一个推动，因为与它相邻的四个空间都是空的。箱子 2 只能向东或向西推动；它不能向北或向南推动，因为其南侧的空间不为空。箱子 3 不能向任何方向推动。箱子 4 只能向东或向西推动，因为它的南侧有一堵墙。

Sokoban 已被证明是一个 P-Space 完全问题，但我们在这里处理的是一个更简单的变体。在我们这个 Sokoban 的变体中，箱子内部有强力磁铁，它们必须在“几乎”所有时间里保持粘在一起。在“稳定”状态下，所有箱子都应该边与边相连。这意味着从任何一个箱子出发，我们都可以通过共享边的箱子到达任何其他箱子。 如果你推动一个箱子导致箱子不再连通，你就进入了“危险模式”。在危险模式下，下一次推动必须使箱子重新连通。

例如，在下图中：

当前状态是稳定的，因为所有 4 个箱子都边与边相连。假设你决定将最北端的箱子向西推：

现在，我们处于危险模式，因为最北端的箱子没有与其他任何箱子相连。下一次推动必须使我们回到稳定状态。例如，我们可以将那个最北端的箱子向南推：

使箱子再次回到稳定状态。

一个 Sokoban 谜题由一个棋盘、箱子的初始配置和最终配置（我们希望箱子最终所在的位置）组成。

给定一个 EZ-Sokoban 谜题，求出使箱子移动次数最少的解，或者判定它无法解决。最终配置和初始配置都不会处于“危险”模式。 为了简化问题，我们假设你（仓库管理员）可以随时跳到棋盘上的任何空位。

输入格式

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

每个测试用例包含若干行。第一行包含 $R$ 和 $C$，即棋盘的行数和列数，中间用一个空格隔开。接下来是 $R$ 行，每行包含 $C$ 个字符，描述棋盘：

• '.' 是空位
• '#' 是墙
• 'x' 是目标（箱子最终应到达的位置）
• 'o' 是箱子
• 'w' 是箱子且同时是目标

箱子的数量等于目标的数量。

输出格式

对于每个测试用例，输出：

Case #X: K

其中 $X$ 是测试用例编号（从 1 开始），$K$ 是解决该谜题所需的最少箱子移动次数，如果无法解决则输出 $-1$。

数据范围

内存限制：1 GB。

$1 \le T \le 50$

$1 \le R, C \le 12$

小数据集（7 分）

时间限制：4 秒。

$1 \le$ 箱子数量 $\le 2$

大数据集（10 分）

时间限制：6 秒。

$1 \le$ 箱子数量 $\le 5$

样例

输入 1

4
5 4
....
#..#
#xx#
#oo#
#..#
7 7
.######
.x....#
.x....#
..#oo.#
..#...#
.######
.######
4 10
##########
#.x...o..#
#.x...o..#
##########
3 4
.#x.
.ow.
....

输出 1

Case #1: 2
Case #2: 8
Case #3: 8
Case #4: 2