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
ahsanul_haque: 2024-03-24 18:57:55

Yo!! done in one... Just simple BFS

saki10920: 2023-11-06 07:07:49

Got accepted

stubs_fox: 2023-01-24 17:14:41

AC in 4294967296 goes :D so proud

mehraj_mi2: 2023-01-21 11:29:47

AC in one go :X

codertoon: 2023-01-15 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: 2023-01-12 15:29:26

<snip>
[Simes]: Read the footer - Don't post source code here, use the forum.

Last edit: 2023-01-12 16:10:40
avl_tree_10: 2022-09-27 13:45:14

nice question

majay1638: 2022-09-20 15:14:58

For python users try submit in pypy ,
it took me 4 wrong submission to realize it ,
got ac++

bpeter: 2022-08-15 01:31:50

solved in one go

harsh_it2003: 2022-05-11 15:39:51

boom, in second go. first was silly 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