题目背景

战争期间，Robinson 一家希望尽快离开人类帝国。普通航天器都被征用，于是 Joe Robinson 制造了 Robintron——一种只借助行星引力在行星之间跳跃的交通工具。

题目描述

一个恒星系中有 $m$ 颗行星，恒星始终位于原点。每颗行星都沿以恒星为圆心的圆形轨道做匀速逆时针运动。

第 $i$ 颗行星给出：

• 旅程开始时的位置 $(x_i,y_i)$；
• 引力井半径 $r_i$；
• 角速度 $s_i$，单位为弧度/天。

行星本身视为一个点，其轨道半径始终为

Robintron 初始位于第一颗行星，目标是最后一颗行星。

当 Robintron 位于行星 $i$ 上时，它会随行星 $i$ 一起绕恒星运动。如果行星 $i$ 的当前位置进入另一颗行星 $j$ 的引力井，即两颗行星中心之间的距离不超过 $r_j$，Robintron 就可以立即从 $i$ 跳跃到 $j$。跳跃和着陆所需时间忽略不计；跳跃后，Robintron 随行星 $j$ 一起运动。

由于各行星的角速度可能不同，等待某次跳跃机会可能需要一定时间，也可能永远不会出现。

请计算 Robintron 从第一颗行星到达最后一颗行星所需的最短时间。题目保证目标行星一定可达。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

对于每个测试用例：

1. 第一行包含一个整数 $m$（$0<m<1000$），表示行星数量，不包括位于原点的恒星。
2. 接下来 $m$ 行，每行包含四个数 $x_i,y_i,r_i,s_i$：
   • $-10^{10}\le x_i,y_i\le 10^{10}$；
   • $0<r_i\le 10^5$；
   • $0\le s_i\le 2\pi$。

所有行星均逆时针旋转，$s_i$ 的单位为弧度/天。

旅程始终从输入中的第一颗行星出发，以最后一颗行星为目的地。恒星不能用于跳跃。

输出格式

对于每个测试用例，输出一行一个整数：最短旅行时间向上取整后的天数。

若目标行星可以立即到达，则输出 0。

样例输入

2
3
10.0 0.0 1.0 1.570796325
-13.0 0.0 3.1 3.14159265
17.0 0.0 4.1 0.0
5
10.0 0.0 1.1 1.0
12.0 0.0 1.1 2.0
13.0 0.0 1.1 1.0
0.0 11.0 1.1 3.14159265
14.0 0.0 1.1 1.0

样例输出

3
7