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

hide comments
abhilash08: 2016-06-20 23:02:07

Getting TLE, implemented normal BFS. I did my code in JAVA.

ABHISHEK BERA: 2016-06-12 14:35:03

for Java users ... BufferedReader .. BufferedWriter + proper implementation will get u AC

ov3rk1ll: 2016-06-12 10:24:33

do some precalculations

Last edit: 2016-06-12 11:21:09
jaskirat15: 2016-06-12 07:58:13

I've been stuck on this problem for days now. Can the admin please help me with this.
All the test cases that have come up on my mind, my code seems to produce the desired result for it.
Yet I keep getting WAs.
Thanks.

macbox: 2016-06-10 20:33:29

Admin can u tell why my rest of the solutions were not working.

macbox: 2016-06-10 20:30:14

This problem consists lots of bugs first of all it won't work if 't' (no of test case) is not declared short.I don't know what the problem is.

Sachin Bisht : 2016-04-20 20:29:12

@admin, @krishnannakul what is the time limit in case of JAVA. I am getting TLE

Last edit: 2016-04-20 20:30:04
minhthai: 2016-01-18 16:11:44

how to do this in java :(( < 1000 operations for example tests and still TLE

gaurav_994: 2016-01-08 09:14:19

@admin what is the time limit for this problem i am getting tle at 0.16.should i use fast input ?(java)

sidpandey: 2015-12-10 16:19:44

nice problem....accepted in the 2nd attempt....not bad :)


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