I. Best Sun
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

Ivan likes painting. He decided to paint a sun.

To do that, he took $$$n$$$ points with integer coordinates on the plane. Ivan will draw segments connecting some pairs of points to get the best sun.

  • Ivan will connect exactly $$$n$$$ pairs of points with segments between them.
  • All segments should not intersect (except for endpoints).
  • There should be exactly one cycle. This cycle should be a convex polygon.
  • Each point that is not one of the polygon vertices should lie outside of the polygon and should be connected with one of the polygon's vertices.
  • It is possible that all vertices will lie on the cycle.

Ivan wants to paint a bright, pretty sun. So he came up with the score of the sun:

  • Let us define $$$S$$$ as the area of the polygon.
  • Let us define $$$P$$$ as the sum of lengths of all drawn segments.
  • The value $$$\displaystyle \frac{S}{P}$$$ is the score of the sun.

What is the maximum possible score of the sun?

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 300$$$) — the number of points.

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$|x_i|, |y_i| \leq 10^6$$$). All points are different. No three points lie on the same line.

It is guaranteed that the sum of $$$n^2$$$ for all test cases does not exceed $$$90\,000$$$.

Output

For each test case, print a single real number — the maximum possible score of the sun that can be drawn.

The absolute or relative error should not exceed $$$10^{-6}$$$.

Example
Input
4
3
-1 -1
1 -1
0 1
4
0 0
10 0
0 10
8 1
5
2 0
-2 0
1 1
-1 1
0 3
8
4 4
-4 4
4 -4
-4 -4
5 6
-6 5
-5 -6
6 -5
Output
0.3090169943749474
1.2368614277111258
0.2711375415034555
1.5631002094915825
Note

The picture of the sun with the maximum score in the fourth test case:

For this sun, $$$S = 64$$$, $$$P = 32 + 4\sqrt{5}$$$, so its score is $$$\displaystyle \frac{64}{32+4\sqrt{5}}$$$.