**12 人解决**，39 人已尝试。

**19 份提交通过**，共有 95 份提交。

**7.3** EMB 奖励。

**单点时限: **2.0 sec

**内存限制: **256 MB

A chessboard has 8 rows and 8 columns, you can see it below. Give you knight, queen, rook’s positons. You should determine the minimal number of moves the knight needs to capture both the rook and the queen, assuming neither of them moves. You may capture them in either order - rook first or queen first.

The first line of input gives the number of cases, N(1 ≤ N ≤ 100). N test cases follow.

Each test case consists of three string: knight’s positon, queen’ positon and rook’s positons. The position will be formatted as “cr”, where c is a character between ‘a’ and ‘h’, inclusive, determining the row on the board (‘a’ is the lowest, ‘h’ is the highest), and r is a digit between ‘1’ and ‘8’, inclusive, determining the column (1 is the first column, 8 is the last).

For each test case,output the minimal number of moves the knight needs to capture both the rook and the queen.

Note:

*A knight’s jump moves him 2 cells along one of the axes, and 1 cell along the other one. In other words, if knight is in the (0,0) now, it can be in (-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2) or (1, 2) after his move.

*The knight cannot jump out of the board.

Input

3 a1 b3 c5 b1 c3 a3 a1 a2 b2

Output

2 3 6 Hint: For Case 1: As show in picture one ,from "a1", the knight can move directly to "b3" and capture the rook. From there, the knight can move directly to "c5" and capture the queen. For Case 2: The rook and the queen are both 1 move away from the knight. Once the knight captures one of them (it doesn't matter which one), it can return to its starting location, and capture the other piece in one more move. For Case 3:The rook and the queen are close, but it takes 6 moves to capture them.

**12 人解决**，39 人已尝试。

**19 份提交通过**，共有 95 份提交。

**7.3** EMB 奖励。

题目标签