# [Solution] Deadly Laser solution codeforces

Deadly Laser solution codeforces – The robot is placed in the top left corner of a grid, consisting of 𝑛n rows and 𝑚m columns, in a cell (1,1)(1,1).

In one step, it can move into a cell, adjacent by a side to the current one:

• (𝑥,𝑦)(𝑥,𝑦+1)(x,y)→(x,y+1);
• (𝑥,𝑦)(𝑥+1,𝑦)(x,y)→(x+1,y);
• (𝑥,𝑦)(𝑥,𝑦1)(x,y)→(x,y−1);
• (𝑥,𝑦)(𝑥1,𝑦)(x,y)→(x−1,y).

The robot can’t move outside the grid.

The cell (𝑠𝑥,𝑠𝑦)(sx,sy) contains a deadly laser. If the robot comes into some cell that has distance less than or equal to 𝑑d to the laser, it gets evaporated. The distance between two cells (𝑥1,𝑦1)(x1,y1) and (𝑥2,𝑦2)(x2,y2) is |𝑥1𝑥2|+|𝑦1𝑦2||x1−x2|+|y1−y2|.

Print the smallest number of steps that the robot can take to reach the cell (𝑛,𝑚)(n,m) without getting evaporated or moving outside the grid. If it’s not possible to reach the cell (𝑛,𝑚)(n,m), print -1.

The laser is neither in the starting cell, nor in the ending cell. The starting cell always has distance greater than 𝑑d to the laser.

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of testcases.

The only line of each testcase contains five integers 𝑛,𝑚,𝑠𝑥,𝑠𝑦,𝑑n,m,sx,sy,d (2𝑛,𝑚10002≤n,m≤10001𝑠𝑥𝑛1≤sx≤n1𝑠𝑦𝑚1≤sy≤m0𝑑𝑛+𝑚0≤d≤n+m) — the size of the grid, the cell that contains the laser and the evaporating distance of the laser.

The laser is neither in the starting cell, nor in the ending cell ((𝑠𝑥,𝑠𝑦)(1,1)(sx,sy)≠(1,1) and (𝑠𝑥,𝑠𝑦)(𝑛,𝑚)(sx,sy)≠(n,m)). The starting cell (1,1)(1,1) always has distance greater than 𝑑d to the laser (|𝑠𝑥1|+|𝑠𝑦1|>𝑑|sx−1|+|sy−1|>d).

For each testcase, print a single integer. If it’s possible to reach the cell (𝑛,𝑚)(n,m) from (1,1)(1,1) without getting evaporated or moving outside the grid, then print the smallest amount of steps it can take the robot to reach it. Otherwise, print -1.

Example
input

Copy
3
2 3 1 3 0
2 3 1 3 1
5 5 3 4 1
output

Copy
3
-1
8