Problem Description

On a 2D plane, there are $n$ ants. Each ant has a line segment as its movement range. The two endpoints of the $i$-th ant’s movement range are $(u_i^x, u_i^y)$ and $(v_i^x, v_i^y)$. Now the ants plan to set meeting centers at the intersection points of these segments. To save as much budget as possible, they decide to set meeting centers only at intersection points that are lattice points (points with integer coordinates). How many meeting centers need to be set?

Input Format

The input consists of $n + 1$ lines.

The first line contains a positive integer $n$.

The next $n$ lines each contain $4$ integers separated by spaces, representing $u_i^x, u_i^y, v_i^x, v_i^y$.

Output Format

Output one line containing one integer, representing the answer.

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

2

Hint

Sample Explanation.

Among all segments, there are $3$ distinct intersection points: $(0, 4)$, $(\frac{4}{3}, \frac{4}{3})$, and $(2, 2)$. Among them, there are $2$ lattice points: $(0, 4)$ and $(2, 2)$.

Constraints.

For $20\%$ of the testdata, it is guaranteed that $0 \le u_i^x, u_i^y, v_i^x, v_i^y \le 100$.

For $100\%$ of the testdata, it is guaranteed that $n \le 500$ and $0 \le u_i^x, u_i^y, v_i^x, v_i^y \le 10000$. It is guaranteed that no ant’s movement range degenerates into a point. It is not guaranteed that the number of intersection points between any two segments is finite.

Translated by ChatGPT 5