CF1721B.Deadly Laser

The robot is placed in the top left corner of a grid, consisting of $n$ rows and $m$ columns, in a cell $(1, 1)$.

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

• $(x, y) \rightarrow (x, y + 1)$;
• $(x, y) \rightarrow (x + 1, y)$;
• $(x, y) \rightarrow (x, y - 1)$;
• $(x, y) \rightarrow (x - 1, y)$.

The robot can't move outside the grid.

The cell $(s_x, s_y)$ 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 $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.

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.

机器人被放置在一个由 $n$ 行 $m$ 列组成的网格的左上角，即位置 $(1, 1)$。

每一步，机器人可以移动到与当前所在格子上下左右相邻（即共享一条边）的格子中：

• $(x, y) \rightarrow (x, y + 1)$；
• $(x, y) \rightarrow (x + 1, y)$；
• $(x, y) \rightarrow (x, y - 1)$；
• $(x, y) \rightarrow (x - 1, y)$。

机器人不能移出网格边界。

格子 $(s_x, s_y)$ 中装有一台致命激光发射器。若机器人进入某个与该激光器的曼哈顿距离不超过 $d$ 的格子，则会被瞬间蒸发。两个格子 $(x_1, y_1)$ 与 $(x_2, y_2)$ 之间的距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

请输出机器人在不被蒸发且不移出网格的前提下，到达目标格子 $(n, m)$ 所需的最少步数；若无法到达 $(n, m)$，则输出 $-1$。

激光器所在格子既不是起点 $(1, 1)$，也不是终点 $(n, m)$；且起点 $(1, 1)$ 到激光器的距离严格大于 $d$。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The only line of each testcase contains five integers $n, m, s_x, s_y, d$ ($2 \le n, m \le 1000$; $1 \le s_x \le n$; $1 \le s_y \le m$; $0 \le d \le 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 ($(s_x, s_y) \neq (1, 1)$ and $(s_x, s_y) \neq (n, m)$). The starting cell $(1, 1)$ always has distance greater than $d$ to the laser ($|s_x - 1| + |s_y - 1| \gt d$).

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例仅有一行，包含五个整数 $n, m, s_x, s_y, d$（$2 \le n, m \le 1000$；$1 \le s_x \le n$；$1 \le s_y \le m$；$0 \le d \le n + m$）—— 分别表示网格的尺寸、激光所在单元格的坐标，以及激光的蒸发距离。

激光既不在起点单元格，也不在终点单元格（即 $(s_x, s_y) \neq (1, 1)$ 且 $(s_x, s_y) \neq (n, m)$）。起点单元格 $(1, 1)$ 到激光的距离恒严格大于 $d$（即 $|s_x - 1| + |s_y - 1| \gt d$）。

For each testcase, print a single integer. If it's possible to reach the cell $(n, m)$ from $(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.

对于每个测试用例，输出一个整数。如果机器人能够从 $(1, 1)$ 出发，在不被蒸发且不移出网格的前提下到达单元格 $(n, m)$，则输出机器人到达该位置所需的最少步数；否则，输出 $-1$。