小青魚想要將 $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}$。