百慕大三角 — 大西洋上的一个神秘区域,据传言,船只和飞机在这里消失得无影无踪。有些人归咎于磁异常,另一些人则归咎于通往其他世界的门户,但真相仍然隐藏在神秘的迷雾中。
一个晴朗的晴天,一趟定期客运航班 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$$$。
示例
输入复制
66 2 2 5 26 2 2 20 84 1 2 1 14 1 1 1 24 1 1 2 16 2 3 2 3
输出复制
2 2 -1 -1 -1 5
注意
第一个测试用例的说明如下:
在第二个测试用例中,答案与第一个测试用例相同,因为除速度之外的所有初始数据都相同,但飞机最初朝同一方向移动。
在第三个测试用例中,答案是 $$$-1$$$,因为飞机将仅沿着绿色标记的路段移动。下面提供了一个示例: