Little Cyan Fish vill färga $n$ punkter cyan eller vita. Den $i$-te punkten ligger i $(x_i, y_i)$. Punkterna är parvis olika och utgör hörnen i en strikt konvex polygon, angivna i moturs ordning.

Låt $H_c$ vara det konvexa höljet av de cyanfärgade punkterna, och låt $H_w$ vara det konvexa höljet av de vita punkterna. Ett konvext hölje är den minsta konvexa mängden som innehåller de givna punkterna. Det konvexa höljet av en tom mängd är tomt; ett konvext hölje som består av en enda punkt eller ett linjesegment har arean noll.

Bestäm den maximalt möjliga arean av $H_c \cap H_w$, det område som är gemensamt för de två konvexa höljena.

Illustration av de två första testfallen i exemplet (det första till vänster, det andra till höger).

Indata

Det finns flera testfall. Den första raden i indata innehåller ett enda heltal $T$ ($1 \le T \le 10^4$), som anger antalet testfall.

För varje testfall innehåller den första raden ett enda heltal $n$ ($3 \le n \le 10^5$), som anger antalet punkter. Var och en av de följande $n$ raderna innehåller två heltal $x_i$ och $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), som anger koordinaterna för den $i$-te punkten.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett reellt tal, vilket anger den maximalt möjliga arean av snittet mellan de två konvexa höljena.

Ditt svar kommer att accepteras om dess absoluta eller relativa fel inte överstiger $10^{-8}$. Formellt, låt din utskrift vara $a$ och domarnas svar vara $b$; din utskrift accepteras om och endast om $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Exempel

Indata 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

Utdata 1

5.944444444444444444
0
2.458333333333333404

Förklaring

I det första testfallet i exemplet färgar Little Cyan Fish punkterna $1$, $2$, $4$ och $6$ cyan, och de övriga punkterna vita. Den cyanfärgade fyrhörningen och den vita triangeln överlappar i ett område med arean $\frac{107}{18}$, vilket är den maximalt möjliga arean.

I det andra testfallet i exemplet har minst en färg högst två punkter, så snittet har arean noll. Figuren visar punkterna $1$, $3$ och $5$ färgade cyan; det vita konvexa höljet är linjesegmentet som förbinder punkterna $2$ och $4$.

I det tredje testfallet i exemplet ger en färgning av punkterna $1$, $4$ och $6$ i cyan och de övriga punkterna i vitt den maximala snittarean $\frac{59}{24}$.