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 $L$ meters in length and $W$ 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)$ means the North-West corner and $(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) -

Rotate $90^{o}$ clockwise, or

Go forward

**exactly**$x$ meters in the direction the robot is currently facing. But if the distance to the wall in that direction is**strictly**less than $x$ 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)$ position, facing north. They want to move the robot to the $(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)$ to $(c,d)$, or report if it is impossible.

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

The first line of each test case contains two space-separated integers $L$ and $W$ $(1 \leq L,W \leq 10^9)$ denoting the length and the width of the room in meters respectively.

The second line of each test case contains an integer $x$ $(1 \leq x \leq 10^9)$ denoting the distance the robot moves in meters in each ‘‘go forward’’ action if it doesn't crash in the meantime.

The third line contains two space-separated integers $a$ $(0 \leq a \leq L)$ and $b$ $(0 \leq b \leq W)$ denoting the initial coordinates of the robot.

The fourth line contains two space-separated integers $c$ $(0 \leq c \leq L)$ and $d$ $(0 \leq d \leq W)$ denoting the coordinates of the expected destination.

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

if it is impossible.

Input | Output |
---|---|

2 3 3 1 1 1 2 2 3 3 2 2 1 1 1 | 0 1 |

For the first test case, the robot can go $(1,1) \rightarrow (1,2) \rightarrow (2,2)$. For the second test case, the robot can go $(2,1) \rightarrow \textbf{(3,1)} \rightarrow (1,1)$. Here bold letters imply that the robot has encountered a crash. |

Toph uses cookies. By continuing you agree to our Cookie Policy.