Radial and Polygon

Time Limit: 1 Second    Memory Limit: 32768 KB

Given an arbitrary polygon with n vertices p1... pn. Tell at most how many edges can be touched by any single radial from the origin.

Notice that an edge means the line segment between two adjacent vertices, and, a radial is said to touch an edge iff it has at least one point in common with the edge, and also, the origin will never be on the polygon.

Input

There are multiple testcases.

The first line contains only a positive number n (n <= 10000), the number of vertices of the polygon.

The following n lines gives the coordinates of the n points, as the Sample Input shows.

Output

For each testcase, print a line containing only the max number of edges that can be touched.

Sample Input

3
1 0
-1 1
-1 -1

Sample Output

2

Submit

Source: ZOJ Monthly, December 2003