Cats Going Straight

Once upon a time, there was a large mansion surrounded by a high wall. The owner of the mansion loved cats very much and always prepared delicious food for the cats that came to the mansion from time to time. The hungry cats would jump over the high walls and rush to the food that was placed all over the house.

One day, the owner found some cats lying in the house. The cats had been running around the house looking for their food and had bumped into each other or fallen down. For their safety, my husband decided to devise a new place to put their food.

Seen from above, the walls of this house form a polygon. To make it easier for the cats to find their food, the owner decided to place the food only at the vertices of the polygon within the mansion. Also, cats are fickle and you can never predict from which point on the polygon they will enter the house. So the owner decided to place the food in such a way that whichever point the cats entered from, they would be able to go straight to one of the food.

Placing food on all vertices would satisfy this condition. However, it is hard to go around replenishing food, so the master wanted to place food on as few vertices as possible. Now, how many places does the master need to place the food at least?

Create a program that takes as input a polygon representing the walls of a mansion and finds the minimum number of vertices to place the food. However, we assume that the cat can only go straight inside the polygon (edges are included inside the polygon).

Input

The input consists of multiple data sets. The end of the input is indicated by a line with zero one. Each data set is given in the following format.

n
x1 y1
x2 y2
...
xn yn

The first line gives the number of vertices of the polygon, n (3 ≤ n ≤ 16). The following n lines give the coordinates of the vertices of the polygon. Each of the n lines consists of two integers separated by a space. x_i (-1000 ≤ x_i ≤ 1000) denotes the x-coordinate of the i-th vertex, and y_i (-1000 ≤ y_i ≤ 1000) denotes the y-coordinate of the i-th vertex. The vertices of a polygon are given in such an order that adjacent vertices are visited in a counterclockwise direction.

The number of data sets does not exceed 20.

Output

For each data set, output the number of vertices to place food on one line.

Sample Input

8
0 0
3 2
6 2
8 6
6 5
7 7
0 4
3 4
8
0 0
5 3
5 2
4 1
6 1
8 6
6 4
2 4
0

Sample Output

1
2

---