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.

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

3
f6 f6
e2 e4
e2 e3

0
2
3