C. Line-line Intersection
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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

Example
Input
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
Output
1
0
1