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 <= i < j <= 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 <= T <= 1000)$, denoting the number of test cases.
In each test case, there is one integer $n (1 <= n <= 100000)$ in the first line, denoting the number of lines.
For the next $n$ lines, each line contains four integers $x a_i, y a_i, x b_i, y b_i (| x a_i |, | y a_i |, | x b_i |, | y b_i | <= 10^9)$. It means $l_i$ passes both $(x a_i, y a_i)$ and $(x b_i, y b_i)$. $(x a_i, y a_i)$ will never be coincided with $(x b_i, y b_i)$.
It is guaranteed that $sum n <= 10^6$.
For each test case, print a single line containing an integer, denoting the answer.
## Input
The first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there is one integer $n (1 <= n <= 100000)$ in the first line, denoting the number of lines.For the next $n$ lines, each line contains four integers $x a_i, y a_i, x b_i, y b_i (| x a_i |, | y a_i |, | x b_i |, | y b_i | <= 10^9)$. It means $l_i$ passes both $(x a_i, y a_i)$ and $(x b_i, y b_i)$. $(x a_i, y a_i)$ will never be coincided with $(x b_i, y b_i)$.It is guaranteed that $sum n <= 10^6$.
## Output
For each test case, print a single line containing an integer, denoting the answer.
[samples]
**Definitions**
Let $ T \in \mathbb{Z}^+ $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k, m_k \in \mathbb{Z}^+ $ denote the lengths of the plaintext-ciphertext pair and the target ciphertext, respectively.
- Let $ P_k = p_1 p_2 \dots p_{n_k} \in \{A, B, \dots, Z\}^{n_k} $ be the plaintext string.
- Let $ C_k = c_1 c_2 \dots c_{n_k} \in \{A, B, \dots, Z\}^{n_k} $ be the corresponding ciphertext.
- Let $ Q_k = q_1 q_2 \dots q_{m_k} \in \{A, B, \dots, Z\}^{m_k} $ be the target ciphertext to decrypt.
**Constraints**
1. $ 1 \le T \le 50 $
2. $ 1 \le n_k, m_k \le 50 $
3. All strings consist solely of uppercase English letters.
4. The shift $ s_k \in \{0, 1, \dots, 25\} $ mapping $ P_k $ to $ C_k $ is unique and satisfies:
$$
c_i \equiv p_i + s_k \pmod{26}, \quad \forall i \in \{1, \dots, n_k\}
$$
where letters are mapped to integers $ A \to 0, B \to 1, \dots, Z \to 25 $.
**Objective**
For each test case $ k $, determine the shift $ s_k $ from $ P_k $ and $ C_k $, then decrypt $ Q_k $ using the inverse shift $ -s_k \mod 26 $ to obtain plaintext $ D_k = d_1 d_2 \dots d_{m_k} $, where:
$$
d_i \equiv q_i - s_k \pmod{26}
$$
Output $ D_k $ as a string.