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*10⁵, 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