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 (8 × 8). 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 × 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.
Constraints
1 <= T <= 4096
Example
Input: 3 a1 h8 a1 c2 h8 c3 Output: 6 1 4
hide comments
ahsanul_haque:
20240324 18:57:55
Yo!! done in one... Just simple BFS 

saki10920:
20231106 07:07:49
Got accepted


stubs_fox:
20230124 17:14:41
AC in 4294967296 goes :D so proud 

mehraj_mi2:
20230121 11:29:47
AC in one go :X 

codertoon:
20230115 11:30:09
check validity of children cells and reset visited and level array for each test case. :) got AC in 3rd go bcz of a silly mistake. 

hemant0557:
20230112 15:29:26
<snip>


avl_tree_10:
20220927 13:45:14
nice question 

majay1638:
20220920 15:14:58
For python users try submit in pypy ,


bpeter:
20220815 01:31:50
solved in one go 

harsh_it2003:
20220511 15:39:51
boom, in second go. first was silly bad. 
Added by:  Nakul Krishna 
Date:  20120930 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Used for Code it  Vidyut 2012  Amrita University 