A. Daniel and Perpendophobia
time limit per test
1 second
memory limit per test
512 megabytes
input
PHOBIA.INP
output
PHOBIA.OUT

Daniel is a master on Codeforces, thus he is particularly fond of golden color.

Instead of maintaining his streak of master title on Codeforces, Daniel decides to take a day off and goes for real golden treasures in a remote location.

Though the place that he chooses to dig gold is quite complicated, for the sake of simplicity, Daniel models it as the first quadrant of the Cartesian plane:

The place contains $$$N$$$ gold mines in different coordinates. Daniel does not care how much value of gold he could take, but he wants to explore as many gold mines as possible. As he is eager to explore, he considers the following strategy:

  1. He first starts at the origin.
  2. He notes down his current location, which means he records the coordinates of the point he is standing.
  3. As Daniel has trouble with perpendophobia - an extremely rare phobia, he has to avoid certain gold mines. He must avoid a gold mine located at $$$A(x, y)$$$ if and only if there exists a point $$$B(u, v)$$$ in his record that the line that passes through $$$A$$$ and $$$B$$$ is perpendicular with vertical axis $$$Oy$$$ or horizontal axis $$$Ox$$$.
  4. If his current location is a gold mine, he starts digging for treasures.
  5. Then Daniel picks a random gold mine that he does not need to avoid and has not explored yet. If there is no mine satisfying that, he stops there and comes back home, enjoying the gold that he digs.
  6. Or else, he goes from his current location to the location of the chosen gold mine in the straight line, ignoring every mine lying on his way to the chosen gold mine. Once he gets there, he restarts from step 2.

So, can you calculate the maximum number of gold mines that Daniel could explore, if he executes his strategy optimally?

Input

The first line contains integer $$$N (N\ge 1)$$$.

$$$N$$$ lines follow, each line contains 2 integer $$$x, y\ (0\le x, y\le 10^{9})$$$ denoting the coordinate of a gold mine. It is guaranteed that no two gold mines is located on the same spot and no goal mine is located at $$$O(0, 0)$$$.

Integers on the same line are separated by spaces.

Output

A single integer denoting the maximum number of gold mines that Daniel could explore, if he executes his strategy optimally.

Scoring

This problem worths 60 points.

Subtasks:

  1. 5 points: $$$N\le 10$$$.
  2. 15 points: $$$N\le 20$$$.
  3. 20 points: $$$N\le 400$$$.
  4. 20 points: $$$N\le 80000$$$.
Examples
Input
5
100 400
200 200
200 300
300 400
400 100
Output
3
Input
4
0 1
1 2
2 3
3 0
Output
2