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 < 2³¹), 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