Little Cyan Fish quiere colorear $n$ puntos de color cian o blanco. El $i$-ésimo punto está en $(x_i, y_i)$. Los puntos son distintos dos a dos y son los vértices de un polígono estrictamente convexo, enumerados en sentido antihorario.

Sea $H_c$ la envolvente convexa de los puntos de color cian, y sea $H_w$ la envolvente convexa de los puntos blancos. Una envolvente convexa es el conjunto convexo más pequeño que contiene los puntos dados. La envolvente convexa de un conjunto vacío es vacía; una envolvente convexa que consta de un punto o de un segmento de recta tiene área cero.

Halla el área máxima posible de $H_c \cap H_w$, la región común a las dos envolventes convexas.

Ilustración de los dos primeros casos de prueba de ejemplo (el primero a la izquierda, el segundo a la derecha).

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T \le 10^4$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un solo entero $n$ ($3 \le n \le 10^5$), que indica el número de puntos. Cada una de las siguientes $n$ líneas contiene dos enteros $x_i$ e $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), que indican las coordenadas del $i$-ésimo punto.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, imprime una sola línea con un número real, que indique el área máxima posible de la intersección de las dos envolventes convexas.

Tu respuesta será aceptada si su error absoluto o relativo no supera $10^{-8}$. Formalmente, sea $a$ tu salida y $b$ la respuesta del jurado; tu salida se acepta si y solo si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Ejemplos

Entrada 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

Salida 1

5.944444444444444444
0
2.458333333333333404

Nota

En el primer caso de prueba de ejemplo, Little Cyan Fish colorea los puntos $1$, $2$, $4$ y $6$ de cian, y los demás puntos de blanco. El cuadrilátero cian y el triángulo blanco se superponen en un área de $\frac{107}{18}$, que es el área máxima posible.

En el segundo caso de prueba de ejemplo, al menos un color tiene como máximo dos puntos, por lo que la intersección tiene área cero. La figura muestra los puntos $1$, $3$ y $5$ coloreados de cian; la envolvente convexa blanca es el segmento de recta que une los puntos $2$ y $4$.

En el tercer caso de prueba de ejemplo, colorear los puntos $1$, $4$ y $6$ de cian y los demás puntos de blanco produce el área de intersección máxima de $\frac{59}{24}$.