B. Bread
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Natsu is eating bread at Sensei's café when a piece of bread falls onto the floor and starts rolling.

The fallen bread can be regarded as a convex polygon in a two-dimensional plane. Its $$$n$$$ vertices, listed in counterclockwise order, are $$$A_1,A_2,\ldots,A_n$$$. The vertices are pairwise distinct, and no three vertices are collinear. The floor can be regarded as the horizontal line $$$y=0$$$.

Initially, the bread touches the floor along edge $$$(A_n,A_1)$$$. Let the position of vertex $$$A_n$$$ at this moment be the origin. The bread rolls in the positive direction of the $$$x$$$-axis; that is, $$$A_n=(0,0)$$$ and $$$A_1=(x_1,0)$$$, where $$$x_1 \gt 0$$$. The bread then starts rolling. The rolling process can be abstracted as an infinite sequence of rotations performed in order. In the $$$i$$$-th rotation, the entire bread is rotated clockwise about the current position of vertex $$$A_{((i-1)\bmod n)+1}$$$ until $$$A_{(i\bmod n)+1}$$$ touches the floor for the first time, that is, until its $$$y$$$-coordinate becomes $$$0$$$ for the first time.

As a romantic philosopher, Natsu considers the rolling of the bread to be a coincidental and romantic event. For the sake of this romance, after the $$$k$$$-th rotation, Natsu records the distance $$$L(k)$$$ rolled by the bread and the area $$$S(k)$$$ swept out by the bread. You need to calculate their ratio as $$$k$$$ tends to infinity, namely:

$$$$$$ \lim_{k\to +\infty}\frac{S(k)}{L(k)} $$$$$$

The distance $$$L(k)$$$ rolled by the bread after the $$$k$$$-th rotation is defined as the distance from the origin to the position of vertex $$$A_{(k\bmod n)+1}$$$ when the $$$k$$$-th rotation ends. The area $$$S(k)$$$ swept out by the bread after the $$$k$$$-th rotation is defined as the area of the union of all regions covered by the convex-polygon bread at all moments from the beginning of the first rotation to the end of the $$$k$$$-th rotation.

Input

The first line contains one positive integer $$$T$$$ $$$(1\leq T\leq 10^3)$$$, denoting the number of test cases.

For each test case, the first line contains one integer $$$n$$$ $$$(3\leq n\leq 10^5)$$$, denoting the number of vertices of the convex-polygon bread.

The next $$$n$$$ lines each contain two integers $$$x_i,y_i$$$ $$$(0\leq |x_i|,y_i\leq 10^9)$$$. The $$$i$$$-th line denotes the coordinates of vertex $$$A_i$$$ when the bread has just fallen onto the floor.

It is guaranteed that $$$y_1$$$, $$$x_n$$$, and $$$y_n$$$ are all $$$0$$$, and that $$$x_1 \gt 0$$$.

It is guaranteed that vertices $$$A_1,A_2,\ldots,A_n$$$ are pairwise distinct, no three vertices are collinear, and they form a convex polygon in counterclockwise order.

It is guaranteed that the sum of $$$n$$$ over all test cases in one test file does not exceed $$$3\times 10^5$$$.

Output

For each test case, output one floating-point number on one line, denoting the answer. Your answer is considered correct if and only if its relative or absolute error compared with the standard answer does not exceed $$$10^{-9}$$$.

Suppose that your answer is $$$a$$$ and the standard answer is $$$b$$$. Your answer is considered correct if

$$$$$$ \frac{|a-b|}{\max\{b,1\}}\leq 10^{-9} $$$$$$

Example
Input
2
3
2 0
1 5
0 0
4
1 0
1 1
0 1
0 0
Output
4.908664519941197
1.384172075579563
Note

For the first test case, the process from the beginning of the first rotation to the end of the fourth rotation is shown below:

When $$$k=4$$$, we have:

$$$$$$ \begin{aligned} L(k)&=4+3\sqrt{26}\approx19.297058541 \\ S(k)&=\frac{120}{13}+13\sqrt3+\frac{91\pi}{6} +43\arctan\frac15 \approx87.882927382 \end{aligned} $$$$$$