406031: GYM102220 C Line-line Intersection

There are $$$n$$$ lines $$$l_1,l_2,\dots,l_n$$$ on the 2D-plane.

Staring at these lines, Calabash is wondering how many pairs of $$$(i,j)$$$ that $$$1\leq i<j\leq n$$$ and $$$l_i,l_j$$$ share at least one common point. Note that two overlapping lines also share common points.

Please write a program to solve Calabash's problem.

The first line of the input contains an integer $$$T(1\leq T\leq 1000)$$$, denoting the number of test cases.

In each test case, there is one integer $$$n(1\leq n\leq 100000)$$$ in the first line, denoting the number of lines.

For the next $$$n$$$ lines, each line contains four integers $$$xa_i,ya_i,xb_i,yb_i(|xa_i|,|ya_i|,|xb_i|,|yb_i|\leq 10^9)$$$. It means $$$l_i$$$ passes both $$$(xa_i,ya_i)$$$ and $$$(xb_i,yb_i)$$$. $$$(xa_i,ya_i)$$$ will never be coincided with $$$(xb_i,yb_i)$$$.

It is guaranteed that $$$\sum n\leq 10^6$$$.

For each test case, print a single line containing an integer, denoting the answer.

3
2
0 0 1 1
0 1 1 0
2
0 0 0 1
1 0 1 1
2
0 0 1 1
0 0 1 1

1
0
1