题目描述

称平面上的三条线段组成一个 K 形图案，当且仅当满足：

1. 其中两条线段拥有一个公共端点；
2. 这个公共端点严格位于第三条线段的内部；
3. 前两条线段位于第三条线段的同一侧；
4. 三条线段两两不共线。

下图左侧给出了合法的 K 形图案，右侧给出了不合法的情况：

给定平面上的 $n$ 条线段，求其中有多少组三条线段能够组成 K 形图案。

输入格式

输入包含多组测试数据。

第一行包含整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含整数 $n$，表示线段数量；

• 接下来 $n$ 行，第 $i$ 行包含四个整数

  $$x_{i,1},y_{i,1},x_{i,2},y_{i,2},$$

  表示第 $i$ 条线段两个端点的坐标。

所有线段长度均为正，但不同线段可能完全重合。

数据范围

所有测试数据的 $n$ 之和不超过 $10^4$。

输出格式

对于每组测试数据，输出一行一个整数，表示能够组成 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