在 $xy$ 平面上给定 $N$ 条直线。第 $i$ 条直线 $\ell_i$ 由方程 $a_i x + b_i y + c_i = 0$ 表示。令 $P$ 为这些直线之间所有交点的集合，定义如下：

$$P = \{p \in \mathbb{R}^2 \mid \exists i, j \in \{1, 2, \dots, N\} \text{ 使得 } p \in \ell_i, p \in \ell_j, i \neq j\}$$

求 $P$ 的凸包面积。如果凸包为空、是一个点或一条线段，则面积视为 0。

你有 $T$ 组测试数据；请解决每一组数据。

凸包的定义

有限集 $S = \{x_1, \dots, x_{|S|}\}$ 的凸包 $\text{conv}(S)$ 定义如下：

$$\text{conv}(S) = \left\{ \sum_{i=1}^{|S|} \alpha_i x_i \;\middle|\; \sum_{i=1}^{|S|} \alpha_i = 1, 0 \le \alpha_i \le 1 \right\}$$

输入格式

输入通过标准输入给出，格式如下：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每个测试用例的格式如下：

$N$ $a_1 \ b_1 \ c_1$ $a_2 \ b_2 \ c_2$ $\vdots$ $a_N \ b_N \ c_N$

数据范围

• $1 \le T$
• $2 \le N \le 10^4$
• $|a_i|, |b_i|, |c_i| \le 10^3$
• $a_i \neq 0$ 或 $b_i \neq 0$
• 任意两条直线 $\ell_i$ 和 $\ell_j$ 均不相同 ($i \neq j$)
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$
• 所有输入值均为整数

输出格式

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

当你的输出与实际答案的绝对误差或相对误差不超过 $10^{-5}$ 时，将被视为正确。

样例

样例输入 1

3
4
1 -1 -2
3 3 -6
-1 2 -4
1 2 4
3
3 0 5
5 0 18
1 0 7
3
314 159 -1
313 158 -1000
315 160 999

样例输出 1

72.0
0
0.0016129032

说明

在第一个样例中，$P$ 的凸包形成了一个三角形，连接点 $(8, 6), (-4, 0)$ 和 $(8, -6)$，面积为 72。

在第二个样例中，由于三条直线均平行，因此 $P = \emptyset$，这意味着凸包的面积为 0。