Description

In a 2D Cartesian coordinate system, there are $n$ lines. No three lines intersect at one point, and no two lines coincide. Obviously, these lines form at most $\dfrac{n(n-1)}{2}$ intersection points. You may choose a subset of these lines. A point is considered covered if and only if at least one of the chosen lines passes through it. Find the minimum number of lines to choose so that all intersection points are covered.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain three integers $a, b, c$, describing a line with equation $ax+by+c=0$.

Note: the input does not guarantee $\gcd(a,b)=1$.

Output Format

Output one line with one integer, representing the answer.

3
1 2 3
4 5 6
7 8 10

2

Hint

For $100\%$ of the testdata, $1 \le n \le 10^5$, $|a|, |b|, |c| \le 10^9$, and $a, b$ are not both $0$.

Sample Explanation

One way is to choose the two lines $x+2y+3=0$ and $4x+5y+6=0$.

It can be proven that there is no better solution.

Translated by ChatGPT 5