我们称平面上的三条线段构成一个 K 形图形，如果： 其中两条线段共享一个公共端点； 该公共端点位于第三条线段的内部（非端点）； 这两条线段位于第三条线段的同一侧； 三条线段两两不共线。

有效的 K 形图形与无效的 K 形图形

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

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

输出格式

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

样例

输入 1

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

输出 1

6
2