NAKANJC - Minimum knight moves Challenge

Anjali and Nakul are good friends. They had quarrelled and you had written a program for Anjali 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 knows Anjali didn't write it herself and says her program is too slow by all standards. He is 

unimpressed so she asks you to try solve the problem faster this time using as few keystrokes as possible.

She wants to know whether you can actually do it. Anjali is very weak in programming. Help her to solve the 

problem.

 Since you are busy and tend to forget she reminds you that "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).

 Since you are busy and tend to forget she reminds you that-

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

first solve problem http://www.spoj.com/problems/NAKANJ/

Input

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

space.

T<=200001

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


Output

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

Example

Input:
3
a1 h8
a1 c2
h8 c3
Output:
6
1
4
Score:
Your source code length (if you are successful in avoiding TLE and WA)
The smaller code the better
EDIT: Time limit increased 28-11-2012. All submissions rejudged

Added by:Aditya Pande
Date:2012-11-26
Time limit:0.100s-1s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own

hide comments
2018-03-01 06:18:52
Cut 4059 B of fully documented wonderfull C++ code to 658 B of unreadable junk. And still did not crack top 100 :(.

Last edit: 2018-03-01 06:24:40
2016-08-01 07:44:45
C in 365B.
2014-04-13 10:00:56 nadavishe
Haskell - 319 B

Last edit: 2014-04-13 10:01:23
2012-12-26 07:27:08 Aditya Pande
i would like to congratulate language wise best submissions:
Béla Mérvadó for C 243 B
Mitch Schwartz for Ruby 133 B
Mitch Schwartz for Perl 109 B
demacek for PAS 337 B


Last edit: 2013-01-08 07:17:42
2012-12-13 08:28:36 Aditya Pande

Hints:

1. don't include any library you dont need
2. get rid of all whitespaces
3. Remove all comments as they don't affect the working of your code
4. try using one letter variable names
5. figure out how to cut down the bytes to the bare minimum to do the task

500B of code is sufficient in C/C++

Last edit: 2012-12-13 08:39:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.