Little Cyan Fish chce pokolorować $n$ punktów na kolor cyjanowy lub biały. $i$-ty punkt znajduje się w $(x_i, y_i)$. Punkty są parami różne i są wierzchołkami ściśle wypukłego wielokąta, podanymi w kolejności przeciwnie do ruchu wskazówek zegara.

Niech $H_c$ oznacza otoczkę wypukłą punktów cyjanowych, a $H_w$ otoczkę wypukłą punktów białych. Otoczka wypukła to najmniejszy zbiór wypukły zawierający dane punkty. Otoczka wypukła zbioru pustego jest pusta; otoczka wypukła składająca się z punktu lub odcinka ma pole równe zero.

Znajdź maksymalne możliwe pole $H_c \cap H_w$, czyli części wspólnej obu otoczek wypukłych.

Ilustracja pierwszych dwóch przykładowych przypadków testowych (pierwszy po lewej, drugi po prawej).

Wejście

Test składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($3 \le n \le 10^5$), oznaczającą liczbę punktów. Każdy z kolejnych $n$ wierszy zawiera dwie liczby całkowite $x_i$ oraz $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), oznaczające współrzędne $i$-tego punktu.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w osobnym wierszu jedną liczbę rzeczywistą, oznaczającą maksymalne możliwe pole części wspólnej obu otoczek wypukłych.

Twoja odpowiedź zostanie zaakceptowana, jeśli jej błąd bezwzględny lub względny nie przekroczy $10^{-8}$. Formalnie, niech Twoje wyjście będzie równe $a$, a odpowiedź jury będzie równa $b$; Twoje wyjście zostanie zaakceptowane wtedy i tylko wtedy, gdy $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Przykład

Wejście 1

3
7
0 0
3 0
4 1
3 3
1 4
-1 3
-1 1
5
0 0
2 0
3 1
1 3
-1 1
7
-1000000000 -1000000000
-500000001 -500000002
499999998 499999995
999999998 999999994
500000000 499999997
-499999999 -500000000
-999999999 -999999999

Wyjście 1

5.944444444444444444
0
2.458333333333333404

Uwagi

W pierwszym przykładowym przypadku testowym Little Cyan Fish koloruje punkty $1$, $2$, $4$ i $6$ na cyjanowo, a pozostałe punkty na biało. Cyjanowy czworokąt i biały trójkąt pokrywają się na obszarze o polu $\frac{107}{18}$, co jest maksymalnym możliwym polem.

W drugim przykładowym przypadku testowym co najmniej jeden kolor ma co najwyżej dwa punkty, więc część wspólna ma pole równe zero. Rysunek przedstawia punkty $1$, $3$ i $5$ pokolorowane na cyjanowo; biała otoczka wypukła to odcinek łączący punkty $2$ i $4$.

W trzecim przykładowym przypadku testowym pokolorowanie punktów $1$, $4$ i $6$ na cyjanowo, a pozostałych punktów na biało daje maksymalne pole części wspólnej równe $\frac{59}{24}$.