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).

knight

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
abuhanif: 2018-11-16 20:05:15

problem AC in vjudge.But in here runtime error(SIGSEGV) why?
plz help

fiorellab2709: 2018-11-01 05:12:10

cant see the image!

sachinspoj: 2018-10-07 07:47:30

good bfs problem;
AC : 2nd go!
adj list not required :)

ameyanator: 2018-09-26 17:41:16

Good problem to learn BFS

sagar_june97p: 2018-09-25 15:43:55

AC in one go!!
My first BFS.

joqsan_77: 2018-08-29 00:32:24

There is no need to construct a graph (this may save you some time).

Last edit: 2018-08-29 00:32:48
ihg_2_26: 2018-08-19 07:25:55

Do care when both strings are same.... XD

selva1996: 2018-06-20 20:04:40

can someone post the image....its not displaying

=(Francky)=> Fixed.

Last edit: 2018-06-20 23:56:32
nidhi_061: 2018-04-04 13:37:22

.

Last edit: 2018-05-31 17:38:13
chetan4060: 2017-12-12 12:13:40

AC in one go!


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