Little Cyan Fish vuole colorare $n$ punti di ciano o di bianco. L'$i$-esimo punto si trova in $(x_i, y_i)$. I punti sono a due a due distinti e sono i vertici di un poligono strettamente convesso, elencati in senso antiorario.

Sia $H_c$ l'inviluppo convesso dei punti ciano e sia $H_w$ l'inviluppo convesso dei punti bianchi. Un inviluppo convesso è il più piccolo insieme convesso che contiene i punti dati. L'inviluppo convesso di un insieme vuoto è vuoto; un inviluppo convesso costituito da un punto o da un segmento di retta ha area zero.

Trova la massima area possibile di $H_c \cap H_w$, la regione comune ai due inviluppi convessi.

Illustrazione dei primi due casi di test di esempio (il primo a sinistra, il secondo a destra).

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 10^4$), che indica il numero di casi di test.

Per ciascun caso di test, la prima riga contiene un singolo intero $n$ ($3 \le n \le 10^5$), che indica il numero di punti. Ciascuna delle successive $n$ righe contiene due interi $x_i$ e $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), che indicano le coordinate dell'$i$-esimo punto.

È garantito che la somma di $n$ su tutti i casi di test non superi $10^5$.

Output

Per ciascun caso di test, stampa una singola riga contenente un numero reale, che indica la massima area possibile dell'intersezione dei due inviluppi convessi.

La tua risposta sarà accettata se il suo errore assoluto o relativo non supera $10^{-8}$. Formalmente, sia $a$ il tuo output e $b$ la risposta della giuria; il tuo output è accettato se e solo se $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Esempi

Input 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

Output 1

5.944444444444444444
0
2.458333333333333404

Note

Nel primo caso di test di esempio, Little Cyan Fish colora i punti $1$, $2$, $4$ e $6$ di ciano e gli altri punti di bianco. Il quadrilatero ciano e il triangolo bianco si sovrappongono in un'area di $\frac{107}{18}$, che è la massima area possibile.

Nel secondo caso di test di esempio, almeno un colore ha al massimo due punti, quindi l'intersezione ha area zero. La figura mostra i punti $1$, $3$ e $5$ colorati di ciano; l'inviluppo convesso bianco è il segmento di retta che congiunge i punti $2$ e $4$.

Nel terzo caso di test di esempio, colorare i punti $1$, $4$ e $6$ di ciano e gli altri punti di bianco fornisce la massima area di intersezione pari a $\frac{59}{24}$.