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 kth 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, 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. Restrictions • 3 ≤ N < 231 Sample Input 3 4 5 18 36 360 2147483647
2/2 Sample Output 1 1 2 3 6 48 1073741823