Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
82 - ZOJ Monthly, August 2009 - D
Protect the King

Time Limit: 1 Second      Memory Limit: 32768 KB

A crowd of people are planning to kill the King, who has been tyrannical for years. The King asks a group of soldiers to protect him. The soldiers stand on the ground, but NO three or more soldiers stand in a single line and NO two of them are at the same point. Each two of them can connect themselves with an iron chain. When some soldiers connect themselves in a CLOSED iron chain circle, a circle of protection is formed. The soldiers can form one, two or more circles, and the King will stand inside all circles of protection, so that it's difficult for the people to break in. The picture below shows an example of "two circles of protection", the red circle indicating the supposed position of the King.

However, when iron chains of different protection circles cross each other, there may well be a chaos when the people try to break in, so it's NOT allowed that chains of different protection circles cross each other. Of course, the more circles of protection, the safer the King. Now given the coordinates of the soldiers, you are asked to calculate the maximal number of protection circles that can form.

Input

There are multiple cases(no more than 25). In each case, there's an integer n ( 2 < n <= 2000) in the first line, indicating the number of soldiers. The second line includes n pairs of integers xi, yi ( 0 <= xi, yi < 100000), indicating the position of the ith soldier.

Output

Print the maximal number of protection circles that can form in one line for each case.

Sample Input

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

Sample Output

1
2


Author: SHE, Jieying
Submit    Status