Crash Course

Limits 2s, 512 MB

Sawda and Alayna have received a remote-controlled toy robot as a gift from their beloved uncle, Mridul. They are happily playing with it together in a rectangular room with LL meters in length and WW meters in width, surrounded by walls in all directions. The walls are parallel to either the North-South line or the East-West line. We can imagine this room with 2D coordinates, where (0,0)(0,0) means the North-West corner and (L,W)(L,W) means the South-East corner. The robot has minimal length and width, you can assume it as a point on the floor. The remote-controlled robot can do the following actions any number of times (possibly zero) -

  1. Rotate 90o90^{o} clockwise, or

  2. Go forward exactly xx meters in the direction the robot is currently facing. But if the distance to the wall in that direction is strictly less than xx meters, it crashes and stops at the wall.

However, the robot cannot rotate while moving or move while rotating.

The robot is currently in (a,b)(a,b) position, facing north. They want to move the robot to the (c,d)(c,d) position. I don't know why. They are children. They do weird things. But they don't want to crash it too many times, because too many crashes can break the toy.

Determine the minimum number of crashes required to move the robot from (a,b)(a,b) to (c,d)(c,d), or report if it is impossible.


The first line contains an integer TT (1T105)(1 \le T \le 10^5) denoting the number of test cases. Each test case is described by four line lines -


For each test case, print an integer in a single line denoting the minimum number of crashes required to go from (a,b)(a,b) to (c,d)(c,d), or print -1 if it is impossible.


3 3
1 1
2 2
3 3
2 1
1 1

For the first test case, the robot can go (1,1)(1,2)(2,2)(1,1) \rightarrow (1,2) \rightarrow (2,2).

For the second test case, the robot can go (2,1)(3,1)(1,1)(2,1) \rightarrow \textbf{(3,1)} \rightarrow (1,1).

Here bold letters imply that the robot has encountered a crash.