你喜欢解谜、水果，以及毫无理由地将蛇和鸟结合在一起的概念吗？如果对这些问题中至少一个的回答是肯定的，那么《Snakebird》可能就是适合你的游戏。通过这个烧脑的益智游戏，帮助蛇鸟们满足它们的食欲。
游戏开始时有一个 $M \times N$ 的网格棋盘，每个格子在初始时属于以下类型之一：
- ‘R’, ‘G’, ‘B’：蛇鸟的头部。棋盘上至少有 1 只，最多 3 只蛇鸟。当你移动一只蛇鸟时，其他蛇鸟被视为障碍物。这意味着你不能进入被其他蛇鸟占据的格子。
- ‘>’, ‘<’, ‘^’, ‘v’：蛇鸟的身体，指向更靠近头部的另一个身体部位。这 4 种类型分别指向右、左、上、下。保证除了最后一个身体部位外，每个头部/身体部位都恰好被另一个身体部位指向。同时也保证每个身体部位都指向一个头部/身体部位。
- ‘.’：空地。蛇鸟可以进入空地。当蛇鸟进入空地时，它的头部进入该格子，所有其他身体部位移动到前一个头部/身体部位的位置。此动作瞬间完成。
- ‘#’：障碍物。蛇鸟不能进入障碍物，但如果蛇鸟的任何部分位于障碍物上方一格，该障碍物就会支撑蛇鸟，使其停止下落。
- ‘|’：尖刺。蛇鸟可以进入尖刺或掉落到尖刺上。然而，如果发生这种情况，蛇鸟就会死亡。
- ‘@’：水果。蛇鸟可以进入水果所在的格子。当蛇鸟进入水果格子时，水果消失，该格子变为普通空地。同时，蛇鸟的所有头部/身体部位保持在原位，蛇鸟在水果所在的格子长出一个新头部。之前的头部变为连接新头部的身体部位。但在蛇鸟下落时，水果被视为障碍物，即使有蛇鸟的头部正向水果掉落。
- ‘X’：出口。棋盘上恰好有 1 个出口。在所有水果消失之前，出口处于非激活状态，就像一个普通空地。在所有水果消失后，任何时候只要蛇鸟的头部位于出口格子，该蛇鸟就会消失并进入天堂。即使蛇鸟正在下落。如果蛇鸟掉落在尖刺上或掉出棋盘，同时它的头部掉进了出口格子，它会在进入天堂前死亡。 :(
在每一步中，你可以选择一只蛇鸟，将其头部移动到相邻的格子（四个方向之一）以进入空地或水果格子。每一步移动后，会发生神奇的事情：你的蛇鸟会受到重力影响，这意味着所有没有支撑的蛇鸟会开始下落，直到它们落到某些障碍物（或其他有支撑的蛇鸟）上或死亡。掉落在尖刺上或掉出棋盘会导致死亡。蛇鸟在下落过程中形状不会改变。
保证初始状态下没有任何东西在下落。
为了帮助 Redbird、Greenbird 和 Bluebird 赢得游戏，你需要将所有蛇鸟活着送入天堂。求出所需的最少移动步数。
输入格式
第一行输入包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含 2 个数字 $M, N$，表示棋盘的行数和列数。接下来的 $M$ 行，每行包含 $N$ 个字符，表示棋盘。
输出格式
对于每个测试用例，输出一行 “Case #x: y”。$x$ 是测试用例编号（从 1 开始），$y$ 是将所有蛇鸟送入天堂所需的最少移动步数。如果无法做到，则输出 -1。
数据范围
- $1 \le T \le 10$
- $1 \le N, M \le 20$
- 棋盘上水果、蛇鸟头部/身体的总数最多为 10。
- 保证初始状态下没有任何东西在下落。
样例
样例输入 1
8 4 4 .... ...v X..G ##.# 4 4 .... ...v X..G #..# 4 4 ..X. .... .R.@ #### 4 7 ....... ....... >>B|..X ####### 4 7 ....... v...... >>B|..X ####### 4 5 >R... ##... ##.X. ##... 4 5 >R... ##... ##|X. ##... 9 11 .......X... ........... ....#...... ........... .#......... .#......... .#..#...B<< ....#..G<<^ .......####
样例输出 1
Case #1: 3 Case #2: -1 Case #3: 6 Case #4: -1 Case #5: 6 Case #6: 2 Case #7: -1 Case #8: 46
说明
在第一个测试用例中，绿色蛇鸟可以向左移动并进入出口。 在第二个测试用例中，由于间隙太大，无法进入出口。 在第三个测试用例中，红色蛇鸟需要向右移动吃掉水果，然后进入出口。 在第四个测试用例中，中间有一个尖刺，长度为 3 的蛇鸟无法穿过。 在第五个测试用例中，长度为 4 的蛇鸟能够穿过。 在第六个测试用例中，蛇鸟可以直接向右移动两次并跳向出口。 在第七个测试用例中，蛇鸟也可以跳向出口，但尖刺会在它到达出口的同时将其杀死。 最后一个样例看起来如下图所示。
