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).
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
bloodgreed99:
20190307 14:50:52
Just like prime paths 

saketag007:
20181207 20:57:08
AC 0.01 easy bfs


abuhanif:
20181116 20:05:15
problem AC in vjudge.But in here runtime error(SIGSEGV) why?


fiorellab2709:
20181101 05:12:10
cant see the image! 

sachinspoj:
20181007 07:47:30
good bfs problem;


ameyanator:
20180926 17:41:16
Good problem to learn BFS 

sagar_june97p:
20180925 15:43:55
AC in one go!!


joqsan_77:
20180829 00:32:24
There is no need to construct a graph (this may save you some time). Last edit: 20180829 00:32:48 

ihg_2_26:
20180819 07:25:55
Do care when both strings are same.... XD


selva1996:
20180620 20:04:40
can someone post the image....its not displaying

Added by:  Nakul Krishna 
Date:  20120930 
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 