Little Cyan Fish は $n$ 個の点をシアンまたは白に塗りたいと考えています。$i$ 番目の点の座標は $(x_i, y_i)$ です。これらの点は互いに異なり、反時計回りに並んだ狭義凸多角形の頂点をなしています。

シアン色の点全体の凸包を $H_c$ とし、白色の点全体の凸包を $H_w$ とします。凸包とは、与えられた点集合を含む最小の凸集合のことです。空集合の凸包は空集合であり、1 点または 1 本の線分からなる凸包の面積はゼロです。

2 つの凸包の共通部分である領域 $H_c \cap H_w$ の面積としてあり得る最大値を求めてください。

最初の 2 つのサンプルテストケースの図（左が 1 番目、右が 2 番目）。

入力

複数のテストケースが与えられます。入力の最初の行には、テストケースの個数を表す単一の整数 $T$ ($1 \le T \le 10^4$) が与えられます。

各テストケースについて、最初の行には点の個数を表す単一の整数 $n$ ($3 \le n \le 10^5$) が与えられます。続く $n$ 行にはそれぞれ、$i$ 番目の点の座標を表す 2 つの整数 $x_i$ と $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) が与えられます。

すべてのテストケースにおける $n$ の総和は $10^5$ を超えないことが保証されます。

出力

各テストケースについて、2 つの凸包の共通部分の面積としてあり得る最大値を表す実数を 1 行に出力してください。

あなたの出力の絶対誤差または相対誤差が $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 番目のサンプルテストケースでは、Little Cyan Fish は点 $1$、$2$、$4$、$6$ をシアンに、残りの点を白に塗ります。シアンの四角形と白の三角形は面積 $\frac{107}{18}$ の領域で重なり、これが達成可能な最大の面積です。

2 番目のサンプルテストケースでは、少なくとも一方の色には高々 2 個の点しか含まれないため、共通部分の面積はゼロになります。図は点 $1$、$3$、$5$ をシアンに塗った場合を示しており、白の凸包は点 $2$ と点 $4$ を結ぶ線分です。

3 番目のサンプルテストケースでは、点 $1$、$4$、$6$ をシアンに、残りの点を白に塗ることで、共通部分の最大面積 $\frac{59}{24}$ が得られます。