NAKANJ - Minimum Knight moves !!!


Anjali and Nakul are good friends. They both had a quarrel recently while playing chess. Nakul wants to know the minimum number of moves a knight takes to reach from one square to another square of a chess board (8X8). Nakul is brilliant and he had already written a program to solve the problem. Nakul wants to know whether Anjali can do it. Anjali is very weak in programming. Help her to solve the problem.

A knight can move in the shape of an "L" in a chessboard - two squares either forward, backward, left, or right and then one square to its left or right. A knight move is valid if it moves as mentioned above and it is within the boundary of the chessboard (8 X 8).

http://0.tqn.com/d/chess/1/0/6/-/-/-/KnightMoves.gif

Input

There are T test cases in total. The next T lines contain two strings (start and destination) separated by a space.

The strings start and destination will only contain two characters - First character is an alphabet between 'a' and 'h' (inclusive), Second character is a digit between '1' and '8' (inclusive) - (Quotes just for clarity).

To know the knight moves more clearly refer to the above figure.

Output

Print the minimum number of moves a knight takes to reach from start to destination in a separate line.

Constarints

1 <= T <= 4096

Example

Input:
3
a1 h8
a1 c2
h8 c3

Output:
6
1
4

hide comments
chetan4060: 2017-12-12 12:13:40

AC in one go!

sonorous: 2017-10-24 15:17:04

AC in one go!!! Indeed a very good question.! It took me sometime to construct the graph .Focus on the movement of the knight and you realise why BFS works here!!!!! That's the key!!

vishesh197: 2017-10-14 06:38:06

very good problem for learning where to apply dfs and where to apply bfs.....focus on this question before solving the problem

Last edit: 2017-10-14 06:38:27
sfialok98: 2017-06-28 21:15:55

After 1st unsuccessful attempt,I was afraid ,how many attempts is this quesion going to take,but got It accepted in the 2nd attempt ..!!
Yippee..!!

Last edit: 2017-06-28 21:16:25
epsilonalpha: 2017-06-26 02:28:49

AC in one go!

Rajat Gautam: 2017-06-12 22:01:25

If facing run time error make sure to give space to nul charater of string for storing.

invinci: 2017-06-11 20:18:09

building the graph took me half an hour, otherwise easy bfs problem, anyways AC in one go ;)

akash619j: 2017-05-02 13:22:00

AC in one go! Thanks to queue and pair stl in c++ :)

nilabja16180: 2017-04-02 09:16:10

AC IN ONE GO!
1st chess problem!

holmesherlock: 2017-03-25 20:00:19

damn irritating runtime error for a very stupid statement missing,otherwise enjoyed doing it


Added by:Nakul Krishna
Date:2012-09-30
Time limit:0.165s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Used for Code it - Vidyut 2012 - Amrita University