机器人被放置在单元格 $$$(1, 1)$$$ 中的网格的左上角,该网格由 $$$n$$$ 行和 $$$m$$$ 列组成。
在一个步骤中,它可以移动到与当前单元格相邻的单元格中:
- $$$(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。
激光既不在起始单元中,也不在结束单元中。起始单元到激光的距离始终大于 $$$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| > d$$$)。
输出
对于每个测试用例,打印一个整数。如果可以从 $$$(1, 1)$$$ 到达单元格 $$$(n, m)$$$ 而不会蒸发或移出网格,则打印机器人到达该单元格所需的最小步数。否则,打印-1。
示例
输入 #1
3 2 3 1 3 0 2 3 1 3 1 5 5 3 4 1
输出 #1
3 -1 8