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

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.

Constraints

1 <= T <= 4096

Example

Input:
3
a1 h8
a1 c2
h8 c3

Output:
6
1
4

Added by:Nakul Krishna
Date:2012-09-30
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

hide comments
2015-12-10 16:19:44
nice problem....accepted in the 2nd attempt....not bad :)
2015-06-29 09:06:16 Deepak Kumar Singh
my first graph prblm......:)
2014-09-17 12:01:10 Deepak Gupta
Remember its 1-8 not 0-7
2014-05-12 23:13:01 Petar Bosnjak
take care of same squares as input...


Last edit: 2014-05-12 23:13:13
2014-04-30 15:11:28 MxNINJA
finally accepted :3
2014-03-22 15:15:01 MxNINJA
it's hard to implement in JAVA :\
TLE :(
2013-12-31 00:06:32 Denys
Hi! I've get SIGSEGV on code submit. But! When I've tried to submit absolutely identically code in NAKANJC - everything was fine (AC). Could you please advise what is going wrong? May be compilation flags or..? g++ 4.3. I've absolutely no idea how it can be possible.
2013-06-22 11:06:17 apsdehal
finally ac after soooooo many WAs', can't neglect smaller cases
2013-06-14 04:16:09 bicky
@Admin,,how can my sol produce 0 for all test cases???........i've checked for all cases,its givin correct ansss...will u pls explain????

Last edit: 2013-06-14 04:16:39
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.