The people think about this problem for several centuries. The programmer Vasechkin’s front office decided to find it out. But the front office is the front office, so the task to find out the answer to the question "How to become a star?" was given to its subordinate Vasechkin.
It’s often happens that account’s and programmer’s notion of the problem much differ. So this time it came off not exactly how the front office has thought. Vasechkin formalized the problem as follows.
is the closed broken line built by the final amount of steps of the following algorithm:
- Fix and arbitrary angle α (0 < α < π).
- The first link is (0, 0) — (1, 0).
- The second link is the resultant of the turn by the angle α counter-clockwise with respect to the point (1, 0) of the first one.
- The (i + 2)-nd link is the resultant of the turn by the angle α counter-clockwise of the (i + 1)-st one with respect to the free end (the opposite to the one that is connected to the i-th link) of the (i + 1)-st link.
- The algorithm stops immediately when the broken line is closed.
Definition. A number of the vertices of the star is the number of the broken line’s links.
The only integer N (3 ≤ N ≤ 100000).
Output an amount of different stars with N vertices.
Problem Author: Pavel Egorov
Problem Source: Open collegiate programming contest for high school children of the Sverdlovsk region, October 11, 2003