21904_AnotherSnake

In this problem, we consider a classic video game called 'Snake'. If you don't know what is, I'll let all-round wikipedia explains to you.

The player controls a long, thin creature, resembling a snake, which roams around on a bordered plane, picking up food (or some other item), trying to avoid hitting its own tail or the "walls" that surround the playing area. Each time the snake eats a piece of food, its tail grows longer, making the game increasingly difficult. The user controls the direction of the snake's head (up, down, left, or right), and the snake's body follows. The player cannot stop the snake from moving while the game is in progress.

--Wikipedia

Recently, we downloaded a new version of Snake. This snake has infinity length, started at (0, 0). Snake can change direction counter-clockwise only at certain points, freely from 0 degree to 180 degrees (include 0 degree but not 180 degrees). Because Snake has infinity length, the total length appeared on screen grows longer and longer, that means, the tail of Snake always locates at (0, 0). The Snake wants to know the maximum pieces of food can be eaten. And, Snake will continue going forward after eating the last one, and it cannot hit itself.

Consider the condition below, after eat the last piece D, the Snake will hit himself. This condition should be considered illegal.

The input contains multiple cases.

For each test case, the first line has one integer n ( n ≤ 15 ), indicates the number of points on the plane.

Following n lines, each line contains two integers, x and y describe the position of a piece of food.

One line for each test case, contains one integer means the maximum number of food can be eaten.

2
0 1
1 0
10
0 1
-1 0
0 -1
1 2
2 -2
-2 1
1 0
-1 -1
1 3
-3 -2

2
10