Background

:::epigraph As the crimson curtain is slowly lifted, you have no way back. Even if the audience is a sky full of gods and Buddhas, or unspeakable disasters... as long as you are still on the stage, this play must go on until the curtain falls. :::

The attachments provide an English PDF version of all problems in this contest, which you may print out for reading.

Problem Description

The stage arranged by Bean is about to begin a wonderful performance...

The stage is a two-dimensional Euclidean plane. Character A initially stands at the center of the stage, i.e., the origin $(0, 0)$. Above the stage there are $n$ spotlights. Each spotlight illuminates a circular region on the plane with center $(x_i, y_i)$ and radius $\sqrt{x_i^2 + y_i^2}$. The circular boundary is also included in the illuminated region. It can be observed that the stage center lies inside the illuminated region of every spotlight.

To make the performance more dramatic, A wants to stay within the illuminated region of every spotlight throughout her movement, and reach the point that is farthest from the stage center.

Help A find the maximum possible distance from the stage center that she can reach, under the condition that her path never leaves the illuminated region of any spotlight.

Input Format

The first line contains an integer $T \ (1 \le T \le 10^5)$, the number of testdata.

For each test case, the first line contains an integer $n \ (1 \le n \le 10^5)$, the number of spotlights.

The next $n$ lines each contain two integers $x_i$ and $y_i \ (-10^5 \le x_i, y_i \le 10^5, \ (x_i, y_i)$ is not the origin), representing the center of a spotlight’s illuminated region.

It is guaranteed that $\sum n \le 3 \times 10^5$ over all test cases.

Within a single test case, it is guaranteed that the centers of any two spotlights are different, and no three spotlight centers are collinear.

Output Format

For each test case, output one real number $d$ on a single line, representing the maximum distance from the stage center that A can reach under the conditions described.

Your answer $d$ will be accepted if the absolute error or relative error between $d$ and the standard answer $ans$ is less than $10^{-6}$.

Formally, your answer $d$ will be accepted if $\frac{|d - ans|}{\max(1, ans)} < 10^{-6}$.

Please control the total precision of your output. Do not output an excessively large file. It is recommended to print no more than 15 digits after the decimal point.

2
2
0 1
1 0
4
1 0
0 1
-1 0
0 -1

1.414213562
0.000000000

Hint

Explanation for Sample 1

:::align{center} :::

The figure above shows the illuminated regions of the spotlights in the first test case. You can see that the farthest point A can reach is $(1, 1)$, so the answer is $d = \sqrt{2}$.

In the second test case, the illuminated regions have no common intersection other than the origin, so the farthest point A can reach is the origin $(0, 0)$, and the answer is $0$.

Translated by ChatGPT 5