Problem Statement

You have a regular N-sided convex polygon. You are going to choose 3 or more vertices from the polygon, and make a new convex polygon P formed by chosen vertices. You very much like equiangular polygons (polygons whose vertex angles are all equal), so the polygon P must be equiangular.

Count the number of equiangular polygons that you can get in the above-mentioned way. Here, two polygons are considered to be the same if they are congruent, that is, one has the same shape and size as the other or as the mirror image of the other.

Constraints

• 3 \leq N \leq 10^{12}

Sample Input 1

6

Sample Output 1

3

You can get following 3 polygons.

Sample Input 2

10

Sample Output 2

4

You can get following 4 polygons.

Sample Input 3

1000000000000

Sample Output 3

749847411091