B. Смертоносный лазер
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Робот стоит в левом верхнем углу поля, состоящего из $$$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.

Лазер не находится ни в начальной, ни в конечной клетке. Начальная клетка всегда находится на расстоянии больше $$$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$$$).

Выходные данные

На каждый набор входных данных выведите одно целое число. Если возможно достичь $$$(n, m)$$$ из $$$(1, 1)$$$, не испепелившись и не выходя за пределы поля, то выведите наименьшее количество шагов, которые может сделать робот, чтобы ее достичь. Иначе выведите -1.

Пример
Входные данные
3
2 3 1 3 0
2 3 1 3 1
5 5 3 4 1
Выходные данные
3
-1
8