Little Cyan Fish ønsker å fargelegge $n$ punkter cyan eller hvite. Det $i$-te punktet ligger i $(x_i, y_i)$. Punktene er parvis forskjellige og utgjør hjørnene i en strengt konveks mangekant, oppgitt i rekkefølge mot klokken.

La $H_c$ være den konvekse innhyllingen av de cyanfargede punktene, og la $H_w$ være den konvekse innhyllingen av de hvite punktene. En konveks innhylling er den minste konvekse mengden som inneholder de gitte punktene. Den konvekse innhyllingen av en tom mengde er tom; en konveks innhylling som består av et enkelt punkt eller et linjestykke har areal lik null.

Finn det maksimalt mulige arealet av $H_c \cap H_w$, området som er felles for de to konvekse innhyllingene.

Illustrasjon av de to første testtilfellene i eksempelet (det første til venstre, det andre til høyre).

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et enkelt heltall $T$ ($1 \le T \le 10^4$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen et enkelt heltall $n$ ($3 \le n \le 10^5$), som angir antall punkter. Hver av de påfølgende $n$ linjene inneholder to heltall $x_i$ og $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), som angir koordinatene til det $i$-te punktet.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder et reelt tall, som angir det maksimalt mulige arealet av snittet mellom de to konvekse innhyllingene.

Svaret ditt vil bli godkjent dersom den absolutte eller relative feilen ikke overstiger $10^{-8}$. Formelt, la utskriften din være $a$ og dommernes svar være $b$; utskriften din godkjennes hvis og bare hvis $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Eksempler

Inndata 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

Forklaring

I det første testtilfellet i eksempelet fargelegger Little Cyan Fish punktene $1$, $2$, $4$ og $6$ cyan, og de øvrige punktene hvite. Den cyanfargede firkanten og den hvite trekanten overlapper i et område med areal $\frac{107}{18}$, som er det maksimalt mulige arealet.

I det andre testtilfellet i eksempelet har minst én farge høyst to punkter, så snittet har areal lik null. Figuren viser punktene $1$, $3$ og $5$ fargelagt cyan; den hvite konvekse innhyllingen er linjestykket som forbinder punktene $2$ og $4$.

I det tredje testtilfellet i eksempelet gir det å fargelegge punktene $1$, $4$ og $6$ cyan og de øvrige punktene hvite det maksimale snittarealet $\frac{59}{24}$.