Description

我们称平面上的三条线段构成一个 ${\it K\text{-}形\ 图形}$，当且仅当满足以下条件：

• 其中两条线段有一个公共端点；
• 这个公共端点严格在第三条线段的内部；
• 这两条线段与第三条线段位于同一侧；
• 这三条线段两两不共线。

给定平面上的 $n$ 条线段，求从中选出的三条线段能构成 $K$ 形图形的三元组数量。

Input Format

每个测试点包含多组测试用例。第一行为测试用例组数 $t$（$1 \le t \le 3333$）。接下来是各组测试用例的描述。

每组测试用例的第一行为一个整数 $n$，表示线段的数量（$3 \le n \le 1000$）。

接下来的 $n$ 行中，第 $i$ 行包含四个整数 $x_{i,1}$、$y_{i,1}$、$x_{i,2}$、$y_{i,2}$，表示第 $i$ 条线段的两个端点的坐标（$-10^6 \le x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2} \le 10^6$）。所有线段长度均大于零，部分线段可能重合。

保证所有测试用例中 $n$ 的总和不超过 $10^4$。

Output Format

对于每组测试用例，输出一个整数，表示能构成 $K$ 形图形的三元组数量。

2
5
0 0 0 10
0 5 3 10
0 5 3 0
0 5 7 4
0 5 6 2
8
0 0 10 10
3 4 4 4
4 4 4 5
3 4 4 4
7 7 7 8
7 7 8 7
5 5 4 6
5 5 3 7

6
2

Hint

由 ChatGPT 4.1 翻译