A wonderful performance is about to begin on the stage set up by cold_beans...
The stage is a 2D Euclidean plane. Character A initially stands at the center of the stage, which is the origin $$$(0, 0)$$$. There are $$$n$$$ spotlights above the stage. Each spotlight projects a circular illuminated area on the plane with its center at $$$(x_i, y_i)$$$ and a radius of $$$\sqrt{x_i^2 + y_i^2}$$$. The boundary of the circle is included in the illuminated area.
To show the tension of the performance, A wants to always stay within the illuminated areas of all spotlights during the performance, and reach the farthest possible point from the center of the stage.
Please help A find the maximum distance from the center of the stage to a point she can reach under the above conditions.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of test cases.
For each test case:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of spotlights.
Each of the following $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$, not both zero) — the coordinates of the center of the illuminated area of a spotlight.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \times 10^5$$$.
It is guaranteed that no two spotlights share the same center, and no three spotlight centers are collinear.
For each test case, output a single real number $$$d$$$ on a new line — the maximum distance from the center of the stage to a point A can reach.
Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
220 11 041 1-1 11 -1-1 -1
1.414213562 0.000000000
The figure above illustrates the illuminated areas of the spotlights in the first testcase. In the first test case, the two spotlights project circles passing through the origin, centered at $$$(0, 1)$$$ and $$$(1, 0)$$$. It can be seen that the farthest point A can reach is $$$(1, 1)$$$, so the answer is $$$d = \sqrt{2} \approx 1.41421356$$$.
In the second testcase, there are no intersecting areas for the illuminated regions other than the origin. Therefore, the farthest point A can reach is the origin $$$(0, 0)$$$, and the answer is $$$0$$$.
