ADACHESS - Ada and Chess

no tags 

Ada the Ladybug was playing chess agains 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 figeres). Also note that it is classical 8x8 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

hide comments
neha1824: 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.

:D: 2018-10-21 17:34:11

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.

:D: 2018-10-21 17:31:54

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
:D: 2018-10-20 16:51:34

Did you take into account cases where x == X and y == Y?

neha1824: 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.


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