Little Cyan Fish souhaite colorier $n$ points en cyan ou en blanc. Le $i$-ème point se trouve en $(x_i, y_i)$. Les points sont deux à deux distincts et forment les sommets d'un polygone strictement convexe, énumérés dans le sens inverse des aiguilles d'une montre.

Soit $H_c$ l'enveloppe convexe des points cyan, et soit $H_w$ l'enveloppe convexe des points blancs. Une enveloppe convexe est le plus petit ensemble convexe contenant les points donnés. L'enveloppe convexe d'un ensemble vide est vide ; une enveloppe convexe constituée d'un point ou d'un segment de droite a une aire nulle.

Trouvez l'aire maximale possible de $H_c \cap H_w$, la région commune aux deux enveloppes convexes.

Illustration des deux premiers cas de test de l'exemple (le premier à gauche, le deuxième à droite).

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T \le 10^4$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un seul entier $n$ ($3 \le n \le 10^5$), indiquant le nombre de points. Chacune des $n$ lignes suivantes contient deux entiers $x_i$ et $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), indiquant les coordonnées du $i$-ème point.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un nombre réel, indiquant l'aire maximale possible de l'intersection des deux enveloppes convexes.

Votre réponse sera acceptée si son erreur absolue ou relative ne dépasse pas $10^{-8}$. Formellement, soit $a$ votre sortie et $b$ la réponse du jury ; votre sortie est acceptée si et seulement si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Exemples

Entrée 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

Sortie 1

5.944444444444444444
0
2.458333333333333404

Remarque

Dans le premier cas de test de l'exemple, Little Cyan Fish colorie les points $1$, $2$, $4$ et $6$ en cyan, et les autres points en blanc. Le quadrilatère cyan et le triangle blanc se chevauchent sur une aire de $\frac{107}{18}$, ce qui est l'aire maximale possible.

Dans le deuxième cas de test de l'exemple, au moins une couleur possède au plus deux points, de sorte que l'intersection a une aire nulle. La figure montre les points $1$, $3$ et $5$ coloriés en cyan ; l'enveloppe convexe blanche est le segment de droite reliant les points $2$ et $4$.

Dans le troisième cas de test de l'exemple, colorier les points $1$, $4$ et $6$ en cyan et les autres points en blanc donne l'aire d'intersection maximale de $\frac{59}{24}$.