Маленька Блакитна Рибка хоче пофарбувати $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}$.