STARSBC - Star
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.
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
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 |