STARSBC - Star

no tags 

Fernando won a compass for his birthday, and now his favorite hobby is drawing stars: first, he marks N points on a circumference, dividing it into N equal arcs; then, he connects each point to the k-th next point, until returning to the first point.

Depending on the value of k, Fernando may or may not reach all points marked on the circumference; when that happens, the star is called complete. For example, when N = 8, the possible stars are shown in the figure below. Stars (a) and (c) are complete, while stars (b) and (d) are not.

Stars for N=8 and k in {1-4}

 

Depending on the value of N, it may be possible to draw many different stars; Fernando asked you to write a program that, given N, determines the number of complete stars he can draw.

Input

The input contains several test cases. Each test case contains a single line, containing a single integer N (3 ≤ N < 231), indicating the number of arcs in which the circumference was divided.

Output

For each test case, your program must print a single line containing a single integer, indicating the number of complete stars that can be drawn.

Example

Input:
3
4
5
18
36
360
2147483647 Output: 1
1
2
3
6
48
1073741823

hide comments
Advitiya: 2015-09-20 00:56:08

2 WA due to EOF XO, finally AC, easy one :)


Added by:noname
Date:2015-09-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:Maratona de Programação da SBC Brazil