Маленькая Голубая Рыбка хочет покрасить $n$ точек в голубой (циановый) или белый цвет. $i$-я точка находится в $(x_i, y_i)$. Все точки попарно различны и являются вершинами строго выпуклого многоугольника, перечисленными в порядке обхода против часовой стрелки.

Пусть $H_c$ — выпуклая оболочка голубых точек, а $H_w$ — выпуклая оболочка белых точек. Выпуклая оболочка — это наименьшее выпуклое множество, содержащее данные точки. Выпуклая оболочка пустого множества пуста; выпуклая оболочка, состоящая из одной точки или отрезка, имеет нулевую площадь.

Найдите максимально возможную площадь $H_c \cap H_w$ — общей области двух выпуклых оболочек.

Иллюстрация первых двух тестовых случаев из примера (первый слева, второй справа).

Входные данные

Входные данные состоят из нескольких тестовых случаев. Первая строка входных данных содержит одно целое число $T$ ($1 \le T \le 10^4$) — количество тестовых случаев.

Для каждого тестового случая первая строка содержит одно целое число $n$ ($3 \le n \le 10^5$) — количество точек. Каждая из следующих $n$ строк содержит два целых числа $x_i$ и $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) — координаты $i$-й точки.

Гарантируется, что сумма $n$ по всем тестовым случаям не превышает $10^5$.

Выходные данные

Для каждого тестового случая выведите в отдельной строке одно вещественное число — максимально возможную площадь пересечения двух выпуклых оболочек.

Ваш ответ будет засчитан, если его абсолютная или относительная погрешность не превышает $10^{-8}$. Формально, пусть ваш ответ равен $a$, а ответ жюри равен $b$; ваш ответ засчитывается тогда и только тогда, когда $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Примеры

Входные данные 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

Выходные данные 1

5.944444444444444444
0
2.458333333333333404

Примечание

В первом тестовом случае из примера Маленькая Голубая Рыбка красит точки $1$, $2$, $4$ и $6$ в голубой цвет, а остальные точки — в белый. Голубой четырёхугольник и белый треугольник пересекаются по области площадью $\frac{107}{18}$, что является максимально возможной площадью.

Во втором тестовом случае из примера хотя бы один цвет содержит не более двух точек, поэтому площадь пересечения равна нулю. На рисунке показан случай, когда точки $1$, $3$ и $5$ покрашены в голубой цвет; белая выпуклая оболочка представляет собой отрезок, соединяющий точки $2$ и $4$.

В третьем тестовом случае из примера покраска точек $1$, $4$ и $6$ в голубой цвет, а остальных точек в белый даёт максимальную площадь пересечения, равную $\frac{59}{24}$.