14671467 SUSTech Online Judge
Problem 1467 --Knight

1467: Knight

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 623  Solved: 263
[Submit][Status][Web Board]

Description

We have a chess board. It has 8*8 grids, the index from bottom to top is 1-8, from left to right is a-h. The knight moves a 3*2 square at each step. Give you the start position of the knight, please find the minimum number of steps he should perform to reach the end position.


Input

The first line gives \(t(1\leq t\leq 5000)\) indicating the total number of test data sets. Each subsequent row of t will give a start point and an end point

Output

For each test case, print minimum number of steps needed to reach the end

Sample Input

3
f6 f6
e2 e4
e2 e3

Sample Output

0
2
3

HINT

Source

 

[Submit][Status]