It is during the great war in the year 2240 that the Robinson family decides to leave the human empire, in search for more peaceful and quiet places. The Robinsons already have a planet in mind to which they wish to travel and want to get there as soon as possible. However, because all vehicles capable of spaceflight are being used for the war, the Robinson family has no way to escape to other planets by means of ordinary spaceflight. It is therefore that Joe Robinson, the father of the family, created the Robintron. The Robintron is a vehicle that is capable of travelling from one planet's surface to another by only using the forces of gravity.

It is the gravitational pull of a planet that keeps the Robintron on a planet's surface. This pull extends as far as the planet's gravity well, a circular area around the center of the planet, which is generated by the planet's mass. However, these gravity wells can also be used to assist the Robintron in leaving a planet by the way of planet hopping. Planet hopping can be performed when the Robintron is on the surface of a planet and comes within the area of another planet's gravity well. The Robintron uses the other planet's gravity well to gain enough momentum to escape into space, and to land on the other planet's surface. Leaving a planet and subsequently landing on another one takes no significant amount of time.

Planet hopping has some disadvantages. The Robintron must be within the gravity well of a planet other than the one it resides on, to be able to effectively use it for planet hopping. However, as the planets rotate around a star (which they all do in perfectly circular orbits), their position continuously changes according to their rotational speed. Thus, it can take up some time for the Robintron to enter the gravity well of a particular planet. Also, as soon as the Robintron chooses to enter the gravity well of a planet, it will move along with that planet around the star. Therefore, this could mean that another planet's gravity well may never come in reach of the Robintron.

Given a list of planets in a star system, a starting position and destination, write a program that determines how many days it will take (using the ceiling function, i.e. ceiling(2.3) = 3) for the Robintron to travel to its destination, given that it travels via the fastest route possible.

Because in most star systems all planets are positioned around the star in a disc, only two dimensions have to be taken into account. Also, a planet is assumed to be a single point in space, and the Robintron's coordinates are equal to those of the planet it resides on.

Input

The first line of input consists of the integer number n, the number of test cases;

Then, for each test case:

A line containing the positive integer number m (0 < m < 1000), the number of planets in the star system (excluding the star which always resides at position [0, 0]);

Per planet a line containing 4 floating-point numbers x (-1e10 <= x <= 1e10) and y (-1e10 <= y <= 1e10), the x-coordinate and y-coordinate of the planet relative to the star at the start of the Robintron's journey respectively; r (0 < r <= 1e5) the radius of the planet's gravity well and s (0 <= s <= 2 * Pi) the speed, in radians per day, at which the planet rotates (counterclockwise) around the central star. The numbers are separated by a space.

The Robintron's journey always starts at the first listed planet and its destination is always the last listed planet, which is always reachable from the Robintron's starting position. The star (at position [0, 0]) is too hot for the Robintron and cannot be used for planet hopping.

Output

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

Example

Input:
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
Output:
3
7