Robintron

During the great war of the year 2240, the Robinson family decides to leave the human empire in search of more peaceful and quiet places. They already have a destination planet in mind and want to reach it as quickly as possible. However, because every spaceflight-capable vehicle has been requisitioned for the war, the Robinsons have no way to escape to other planets by ordinary space flight. So Joe Robinson, the father of the family, builds the Robintron: a craft that can travel from the surface of one planet to another using only the force of gravity.

It is a planet's gravity that keeps the Robintron on its surface. That pull reaches out as far as the planet's gravity well, a circular region of radius $r$ centered on the planet and generated by its mass. A gravity well can also be used to leave a planet, by planet hopping. A hop can be performed when the Robintron, sitting on the surface of one planet, comes to lie inside the gravity well of a different planet: it borrows that other planet's well to gain enough momentum to escape into space and land on that planet's surface. Leaving one planet and landing on another takes no significant amount of time.

Planet hopping has a catch. To hop, the Robintron must be inside the gravity well of a planet other than the one it is standing on. Because all the planets orbit the central star in perfectly circular orbits, their positions change continuously according to their own angular speeds, so it can take time before a given planet's gravity well comes within reach. Moreover, the instant the Robintron enters a planet's gravity well and hops onto it, the Robintron starts orbiting together with that planet. As a result, some other planet's gravity well may never come within reach.

Given the planets of a star system, a start planet, and a destination planet, write a program that determines how many days the Robintron needs to travel to its destination along the fastest possible route. Days are rounded up with the ceiling function (for example, $\lceil 2.3 \rceil = 3$).

Because the planets of such a system all lie in a disc around the star, only two dimensions have to be considered. Each planet is treated as a single point in space, and the Robintron's coordinates equal those of the planet it is standing on.

The first line contains an integer $n$, the number of test cases. Each test case is given as follows:

• A line with a positive integer $m$ ($0 < m < 1000$), the number of planets in the star system (the star itself always sits at $[0, 0]$ and is not counted).
• Then $m$ lines, one per planet, each with four numbers separated by spaces: $x$ ($-10^{10} \le x \le 10^{10}$) and $y$ ($-10^{10} \le y \le 10^{10}$), the planet's coordinates relative to the star at the start of the journey; $r$ ($0 < r \le 10^5$), the radius of the planet's gravity well; and $s$ ($0 \le s \le 2\pi$), the angular speed in radians per day at which the planet orbits the star counterclockwise.

The Robintron always starts on the first listed planet, and its destination is always the last listed planet, which is always reachable from the start. The star at $[0, 0]$ is too hot to be used for planet hopping.

For each test case, print one line with a single integer: the number of days (rounded up) that the Robintron must travel to reach its destination, or $0$ if it can reach the destination immediately.