H. Optimal Quadratic Function
time limit per test
10 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Two variables $$$x$$$ and $$$y$$$ are dependent to each other with the relation $$$y=f(x)$$$ where $$$f$$$ is a quadratic function: $$$f(x) = a x^2 + b x + c$$$ with some real numbers $$$a$$$, $$$b$$$, and $$$c$$$. However, the function $$$f$$$ is unknown and you want to figure out its best estimation.

For that purpose, you have obtained $$$N$$$ observed $$$y$$$-values $$$y_1, y_2, \ldots, y_N$$$ for $$$x$$$-values $$$x_1, x_2, \ldots, x_N$$$, respectively, by experiments. The observed values $$$y_1, y_2, \ldots, y_N$$$ contain some errors from several sources, so it is unlikely that all of them are exact function values for a certain quadratic function. Therefore, you need to find an optimal estimation of the function $$$f$$$ that minimizes the error.

For any quadratic function $$$f$$$, the error of a data pair $$$(x_i, y_i)$$$ is defined to be $$$(y_i-f(x_i))^2$$$, and the error of $$$f$$$ is defined to be the maximum of these errors over all the $$$N$$$ data pairs. Write a program that, given the $$$N$$$ observed data pairs, finds out an optimal estimation of function $$$f$$$ that minimizes the error and prints out the error value.

Input

The first line contains an integer $$$T$$$, the number of test cases ($$$1 \le T \le 100\,000$$$). The test cases follow.

The first line of each test case contains an integer $$$N$$$, the number of observed data pairs ($$$1 \le N \le 100\,000$$$).

Each of the next $$$N$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$, the $$$i$$$-th data pair ($$$-10^6 \le x_i, y_i \le 10^6$$$).

The sum of $$$N$$$ over all test cases does not exceed $$$200\,000$$$.

Output

For each test case, print a line with a real number: the minimum possible error value.

The answer will be considered correct if its absolute or relative error is within $$$10^{-6}$$$.

Example
Input
1
4
0 0
1 3
2 9
3 0
Output
5.062500000000