ADACHESS - Ada and Chess

Ada the Ladybug was playing chess against her good friend Velvet Mite Vinit. They were talking to each other during the game, saying "I will take your figure in next X moves". After the game, this was really bugging Ada so she have decided to give it more thinking.

As she can't determine it "that fast", she asked you to make a program which could output the minimal number of moves in which two figures could get to each other (note they they don't have to alternate, so all the moves could be done only by one of the figures). Also note that it is classical 8×8 chessboard.

The interesting figures will be: King, Knight, Queen, Tower, Bishop

Input

The first line of input will contain 1 ≤ T ≤ 3*105, the number of test-cases.

Each of the testcases will contain 6 integers f x y F X Y, where 0 ≤ f, F ≤ 4 are the types of figures (0 to 4 standing for King, Knight, Queen, Tower, Bishop in this order) and 0 ≤ x y X Y ≤ 7, the coordinates of given figures.

Output

For each test-case output the minimal number of moves get both figures to same "box". In case the figures can't meet, output "INF".

Example Input

5
1 0 0 1 7 7
2 1 3 3 2 5 
0 1 0 4 5 5
3 1 1 4 3 3
0 1 2 0 3 4

Example Output

6
2
2
1
2

Example Input

10
2 3 6 1 6 2
3 3 6 3 6 7
4 4 6 4 2 4
3 6 0 4 1 0
3 7 1 3 5 2
0 0 6 1 5 4
0 5 7 3 3 5
0 4 1 4 5 3
3 2 1 3 4 2
0 5 2 0 2 7

Example Output

2
2
1
1
2
3
2
2
2
5

Added by:Morass
Date:2017-10-20
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2022-01-19 22:57:01 David
Excellent problem. I see that @neha1824 solved the problem. A hint: There are 252 distinct inputs that take 7 moves.
2021-03-28 07:14:52
A problem to enjoy multiple times. I've designed my solution in several sittings with similar approach as Zukow described, then got AC with Python 2 weeks ago, finally translated to C tonight to cut all the high level-fat. Huge, 260-line program in C, but I'm still quite proud of it. People who move on upon ACing with whatever runtime miss all the fun here.
2018-10-26 08:34:53
Yes I did account for x==X and y==Y cases. I regularly play chess, so I considered all possible moves. I don't know what I am missing.
2018-10-21 17:34:11 :D
Also on the problem itself: it was very fun to code. Took me a while to plan a nice, clean solution that also allowed for optimizations.
2018-10-21 17:31:54 :D
I've prepared a input/output file pair with all possible input combinations, using my AC program. I can send it you if you contact me at jakub{underscore}byczkowski{at}tlen{dot}pl . The condition here is that you will not share this file or use it to set precalc tables in the code. It's for your debug purposes only.

Last edit: 2018-10-21 17:32:41
2018-10-20 16:51:34 :D
Did you take into account cases where x == X and y == Y?
2018-10-18 20:28:42
Getting wrong answer in the 8th test case. I have verified all permutations of input and output but nothing seems wrong. Can anyone help.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.