小青鱼想要将 $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}$。