Background

_Seeking the Stars of Ao_ — Jing (in the seventh year of Jian'an (A.D. 0202))

"On a certain day, there were two close friends, named Jing and Ao, who sought the secrets of the stars. At first, they suffered from having no tools; later, they suffered from having no results. Then chaos ensued, Ao moved away, and his whereabouts became unknown. Can a mere mortal hope to grasp the destiny of the heavens? Truly, their story is lamentable. I write this text to recount it." — Chronicles of Yinghuo

Cosmic Era 1024, Solar Year, 256th Earth Day, in the Strofus star system, "Heshisaji" asteroid mining zone, "Gigak" class advanced mining ship.

Captain Kulo was reading the Chronicles of Yinghuo, written thousands of years ago, which is verified as humanity's first formal observation record of the starry sky with scientific intent, when a series of urgent alarms from the system interrupted him.

"The isolation shield of the secondary tractor bay was damaged by human error," the crew wrote in the system damage report. "Our lovely Princess Konada dragged another huge rock over and chipped the shield, saying she wanted to give it to that kid Maka."

Konada is the captain's daughter, and Maka is the son of the first mate; they could be considered childhood sweethearts.

Captain Kulo began to have a headache again. This is the third time already, and the maintenance department warned last time that there were no more spare isolation shields of the current model.

"You shouldn't blame the lovely Konada," said the captain of the maintenance department. "However, you could try to make a replacement using those that cannot rotate, but I can't calculate how large a hole needs to be cut."

As a member of the mainframe data team, Captain Kulo asks you to help the maintenance department calculate the minimum size of the hole that needs to be cut.

Description

The isolation shield is an important component used to prevent cosmic rays from damaging the scanner (not the tractor!).

Simply put, we can view the isolation shield before cutting as a unit sphere, as shown in the figure below:

The work plan involves $N$ ($1 \leq N \leq 10^6$) observation tasks.

For the $i$-th observation, we start from the point $(0,0)$ and scan a meteorite located at $(x_i, y_i, z_i)$ with radius $r_i$ ($-10^6 < x_i, y_i < 10^6, 0 < r_i < z_i < 10^6$). Here, we can simply treat the meteorite as a sphere.

For each observation, we must ensure that we can scan the entire meteorite through the hole cut in the shield.

Please calculate the radius (arc length of a great circle) of the circular hole we need to cut on the sphere, which is the minimum covering circle of the union of the projections of all meteorite spheres onto the upper unit hemisphere (the circle here is on the surface).

Since it is a unit sphere, this value should be equal to half the plane angle formed by the lines connecting the two points on the diameter of the circular hole to the center of the sphere.

Obviously, this angle $\omega$ satisfies $0 < \omega < \frac{\pi}{2}$. Please output $\lfloor \frac{\omega}{\pi/2} \times 10^5 \rfloor$.

Input

The first line contains an integer $N$, representing the number of observation plans.

Each of the following lines contains four integers, separated by spaces, representing $x_i, y_i, z_i, r_i$ in order.

Output

Output an integer in the range $[0, 99999]$.

Examples

Input 1

5
30 10 10 9
100 -10 100 50
-30 100 50 30
12 42 64 20
287 123 46 31

Output 1

67877

Note 1

The figure below shows the projection of each asteroid onto the shield and the final circular hole cut out.

Note

• This is not a computer graphics problem.
• All characters, times, events, and text in the background story are fictional.
• The input is large; it is recommended to use efficient input/output methods.
• Please make as much use of your algebraic knowledge as possible.