题目描述

你的任务是使用白王、一枚骆驼和一枚宰相将死黑王。

棋子的移动方式如下：

• 骆驼（camel）：用倒置的马图标表示。它进行“加长的马步”，即一个方向移动 $3$ 格，另一个垂直方向移动 $1$ 格；
• 宰相（wazir）：用倒置的车图标表示。它每次沿横向或纵向移动到一个相邻格，即长度为 $1$ 的车步；
• 王（king）：与普通国际象棋中的王相同，每次可以沿横向、纵向或对角线移动到相邻格。

下图给出了三种棋子从 e4 出发时能够一步到达的位置，叉号表示可到达的格子：

本题不采用国际象棋中的“五十回合和棋”规则。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

接下来 $t$ 行，每行依次给出：

1. 白王所在格；
2. 黑王所在格；
3. 白色骆驼所在格；
4. 白色宰相所在格；
5. 字符 w 或 b，表示轮到白方或黑方行动。

棋盘格使用国际象棋代数记谱法表示，由两个字符组成：

• 第一个字符为 a 到 h，表示从左到右的列；
• 第二个字符为 1 到 8，表示从下到上的行。

每组数据均保证：

• 四枚棋子位于互不相同的格子；
• 当前不行动的一方没有处于被将军状态；
• 当前局面尚未结束，即既不是逼和也不是将死局面。

数据范围

输出格式

对于每组测试数据，单独输出一行局面评估：

• 如果在双方最优行动下局面为和棋，输出 0；
• 否则输出字符 #，紧接着输出白方能够保证将死黑王所需的最少步数。

计算将死步数时，只统计实施将杀一方——即白方——的走子次数。

样例

3
f3 f1 f4 g2 w
f3 f1 e1 g2 b
a1 c3 e5 h8 b

#1
0
#66

样例局面如下：

棋规说明

本题采用以下标准国际象棋规则和概念：

• 双方轮流行动，白方控制白色棋子，黑方控制黑王；
• 行动方每回合必须选择自己的一枚棋子并走一步；
• 棋子不能移动到被己方棋子占据的格子；
• 若移动到被对方棋子占据的格子，则吃掉该棋子，被吃棋子从棋盘上移除；
• 如果一方棋子能够在下一步移动到对方王所在格，则称对方王正受到将军；
• 任何一方都不能走出使自己的王在回合结束时仍受到将军的着法；
• 若轮到行动的一方没有合法着法，且其王未受到将军，则形成逼和，结果为和棋；
• 若轮到行动的一方受到将军且没有合法着法，则形成将死，对方获胜；本题中只有白方可能获胜；
• 若在最优对弈下游戏可以无限进行，则该局面视为和棋。