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

Бермудский треугольник — загадочная область в Атлантическом океане, где, по слухам, бесследно исчезают корабли и самолёты. Одни винят магнитные аномалии, другие — порталы в иные миры, но истина остаётся скрытой в тумане тайн.

Обычный пассажирский рейс 814 следовал из Майами в Нассау в ясный солнечный день. Ничто не предвещало беды, пока самолёт не вошёл в зону странного мерцающего тумана. Радиосвязь прервалась, приборы бешено закрутились, а за иллюминаторами мелькнули вспышки неземного света.

Для простоты будем считать, что Бермудский треугольник и самолёт находятся на плоскости, а вершины треугольника имеют координаты $$$(0, 0)$$$, $$$(0, n)$$$ и $$$(n, 0)$$$. Изначально самолёт находится в точке $$$(x, y)$$$ строго внутри Бермудского треугольника и движется с вектором скорости $$$(v_x, v_y)$$$. Все приборы вышли из строя, поэтому экипаж не может управлять самолётом.

Самолёт может выбраться из треугольника, если он когда-либо окажется ровно в одной из вершин треугольника. Если же в какой-то момент времени (возможно, нецелый) самолёт попадёт на границу треугольника (но не в вершину), то его вектор скорости немедленно отражается относительно этой стороны$$$^\dagger$$$, и самолёт продолжает движение уже в новом направлении.

Определите, сможет ли самолёт когда-либо выбраться из Бермудского треугольника (то есть ровно попасть в одну из его вершин). Если это возможно, также вычислите, сколько раз до этого момента самолёт окажется на границе треугольника (каждое касание границы, даже в одной и той же точке, считается, пересечение вершины — не считается).

$$$^\dagger$$$ Отражение происходит по обычным физическим законам. Угол падения равен углу отражения.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит пять целых чисел $$$n$$$, $$$x$$$, $$$y$$$, $$$v_x$$$ и $$$v_y$$$ ($$$3 \le n \le 10^9$$$, $$$1 \le x, y$$$, $$$x+y \lt n$$$, $$$1 \le v_x, v_y \le 10^9$$$) — числа, описывающие вершины треугольника, изначальные координаты самолёта и изначальный вектор скорости.

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

Для каждого набора входных данных выведите единственное целое число — количество раз, которое самолёт окажется на границе треугольника до того, как выберется из него. Если самолёт никогда не выберется из треугольника, выведите $$$-1$$$.

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

Иллюстрация к первому набору входных данных приведена ниже:

Во втором наборе входных данных ответ такой же, как и в первом, так как все исходные данные, кроме скорости, совпадают, но самолёты изначально движутся в одну и ту же сторону.

В третьем наборе входных данных ответ $$$-1$$$, так как самолёт будет передвигаться исключительно по отрезкам, которые отмечены зелёным цветом. Иллюстрация приведена ниже: