在一个棋盘上有两个白方车（♖）和一个黑方王（♚）。白方先手。你代表白方，需要尽快将死黑方的王。

编写一个程序，确定在黑方采取尽可能延长游戏的最佳策略下，白方将死黑方王所需的最少步数。

关于国际象棋规则的一些说明：

1. 上述描述的局面在标准国际象棋中是不合法的，因为棋盘上没有白方的王。除此之外，游戏规则与国际象棋规则一致。
2. 棋盘大小为 $8 \times 8$ 格。棋盘的列用字母 a 到 h 标记，行用数字 1 到 8 标记。
3. 棋手（白方和黑方）轮流移动一个自己颜色的棋子。在本题中，我们只计算白方移动的步数。
4. 车可以水平或垂直移动任意数量的未被占据的格子。它不能越过其他棋子，也不能与相同颜色的另一个棋子（即另一个白方车）停在同一个格子中。
5. “将军”是指在下一步棋中威胁要吃掉王，即其中一个车与王处于同一行或同一列的局面。
6. 王可以向任何方向（水平、垂直或对角线）移动一格，除非该移动会使王处于被“将军”的状态。如果满足此条件，王可以吃掉已经占领某个格子的车。在这种情况下，该车将从游戏中彻底移除。
7. “将死”是指王受到被吃掉的威胁（即处于被“将军”状态），且没有任何合法的移动来逃脱这种威胁的局面。
8. “逼和”（无子可动）是指轮到某方走子时，该方并未被“将军”，但没有任何合法的走法。国际象棋规则规定，当出现逼和时，游戏以和局结束（这对白方来说是不可接受的）。

输入格式

输入的第一行包含局面的数量（至少为 $1$），接下来的每一行包含一个局面的描述。输入中的所有局面都是不同的。

一个局面由棋盘上三个棋子的位置表示：首先是黑方的王，然后是两个白方的车。保证没有两个棋子占据同一个格子，且初始局面没有被“将军”。

输出格式

对输入中的每个局面输出一行。该行应包含从相应局面开始，白方确保将死黑方所需的最少步数。如果无法达到目标，则对相应的局面输出 $0$。

样例

输入样例 1

2
c7 f1 g6
h6 c3 g8

输出样例 1

2
1