问题描述与实验目的

给定8*8方格棋盘，求棋盘上一只马从一个位置到达另一位置的最短路径长。

注意马是走“日”形的。

输入

输入有若干测试数据。

每组测试数据仅1行，每行上有2个方格pos1、pos2，之间用一个空格隔开，每格方格表示棋盘上的一个位置，该位置由表示列的1个字母（a-h）及表示行的一个数字（1-8）构成，如“d7”表示第4列第7行。

输出

对输入中每行上的2个方格pos1、pos2，输出马从位置pos1跳到pos2所需的最短路径长。如“a1==>a2: 3 moves”表示从位置a1跳到a2所需的最少步数是3。

注意：按输出样例所示格式输出，如“a1==>a2: 3 moves”中冒号后有一个空格，再跟着所需的最少步数。

实验结果

输入样例

a1 a2

a1 a3

a1 h8

g2 b8



输出样例

a1==>a2: 3 moves

a1==>a3: 2 moves

a1==>h8: 6 moves

g2==>b8: 5 moves

-Descr iption and purpose of the experiment

8* 8 grid for a given board, find the board a horse from one location to another location to reach the shortest path length.

Note that horse is to take the "day" shape.

Input

Enter a number of test data.

Only 1 line of each test data, each line has 2 squares pos1, pos2, separated by a space, each grid square, said a board position, the position of column 1 by the said letters ( ah), and that the line of a number (1-8) form, such as "d7" said the line 7 column 4.

Output

Each line in the input box on the two pos1, pos2, output horse to jump from position pos1 pos2 shortest path length required. Such as "a1 ==> a2: 3 moves" that jump from position a1 a2 minimum required number of steps is 3.

Note: The sample shown by the output format of the output, such as "a1 ==> a2: 3 moves" in a space after the colon, and then follow the required minimum number of steps.

Experimental results

Input sample

a1 a2

a1 a3

a1 h8

g2 b8



Sample Ou