Little Cyan Fish는 $n$개의 점을 청록색(cyan) 또는 흰색으로 칠하려고 합니다. $i$번째 점의 좌표는 $(x_i, y_i)$입니다. 점들은 서로 다르며, 반시계 방향 순서로 나열된 엄격한 볼록 다각형의 꼭짓점입니다.

청록색 점들의 볼록 껍질을 $H_c$, 흰색 점들의 볼록 껍질을 $H_w$라고 합시다. 볼록 껍질이란 주어진 점들을 포함하는 가장 작은 볼록 집합입니다. 공집합의 볼록 껍질은 공집합이며, 한 점이나 선분으로 이루어진 볼록 껍질의 넓이는 0입니다.

두 볼록 껍질의 공통 영역인 $H_c \cap H_w$의 가능한 최대 넓이를 구하세요.

처음 두 예제 테스트 케이스의 그림 (왼쪽이 첫 번째, 오른쪽이 두 번째).

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 $T$ ($1 \le T \le 10^4$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 점의 개수를 나타내는 하나의 정수 $n$ ($3 \le n \le 10^5$)이 주어집니다. 이어지는 $n$개의 줄에는 각각 $i$번째 점의 좌표를 나타내는 두 정수 $x_i$와 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)가 주어집니다.

모든 테스트 케이스에서 $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

참고

첫 번째 예제 테스트 케이스에서 Little Cyan Fish는 점 $1$, $2$, $4$, $6$을 청록색으로 칠하고 나머지 점들을 흰색으로 칠합니다. 청록색 사각형과 흰색 삼각형은 넓이 $\frac{107}{18}$만큼 겹치며, 이것이 가능한 최대 넓이입니다.

두 번째 예제 테스트 케이스에서는 적어도 한 가지 색상의 점이 최대 두 개뿐이므로, 교집합의 넓이는 0입니다. 그림은 점 $1$, $3$, $5$를 청록색으로 칠한 경우를 보여주며, 흰색 볼록 껍질은 점 $2$와 점 $4$를 잇는 선분입니다.

세 번째 예제 테스트 케이스에서는 점 $1$, $4$, $6$을 청록색으로 칠하고 나머지 점들을 흰색으로 칠하면 교집합의 최대 넓이인 $\frac{59}{24}$를 얻습니다.