Camel's Right Turn Journey

Byteotia is a land of N oases in the desert, with no three of them collinear. Byteasar lives in one of these oases and has a friend in every other oasis. He wants to visit as many friends as possible by riding his stubborn camel. The camel moves in a peculiar way:

• After leaving an oasis, it moves in a straight line until it reaches the next oasis.
• It turns only at an oasis, and the turn is always to the right (clockwise) by an angle in the interval \([0^\circ,\,180^\circ]\). In other words, if at an oasis the camel comes along a vector \(\vec{v}\) and leaves along \(\vec{w}\), then the angle (in clockwise direction) from \(\vec{v}\) to \(\vec{w}\) must satisfy \(0^\circ \leq \theta \leq 180^\circ\). This is equivalent to requiring that the signed cross product satisfies \(\vec{v}\times\vec{w}\ \le 0\) (with collinear moves, giving an angle of 0° or 180°, being allowed).
• The camel does not want to follow its own footprints. Thus the route (a cycle) cannot pass through any point more than once, except for the starting oasis which is visited twice (at the start and end).

The journey must start and end at Byteasar's oasis. Moreover, the camel initially faces a specific oasis so that the first segment is fixed. In particular, Byteasar's oasis is always the first oasis and the camel initially faces the second oasis. Your task is to determine the maximum number of friends Byteasar can visit following these rules.

inputFormat

The input is read from the standard input and has the following format:

N
x1 y1
x2 y2
... 
xN yN

Here, N (\(3 \le N \le 15\)) is the total number of oases, and the following N lines contain two real numbers each, representing the coordinates of the oases. Byteasar lives at the first oasis, and the camel initially faces the second oasis.

outputFormat

Output to the standard output a single integer: the maximum number of friends Byteasar can visit (i.e. the number of distinct oases visited excluding his own) while satisfying all the journey rules.

sample

3
0 0
1 0
0 1

1