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.

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

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

hide comments
2020-01-20 03:46:38
use scanf , printf and while(scanf("%lld",&n)!=EOF) for input numbers AC
2019-10-10 21:46:40
image link -> https://vj.z180.cn/0dfe6853f57754cccad8cfa7dbd889eb?v=1570280352
2017-05-04 15:49:22
what kind of sorcery is this, WA without EOF.
2016-08-03 15:32:55
getting wrong answers for large values of 'n'.I think the due to large value of 'n' time complexity of the program increases and i am not getting any answer on my console
2015-11-10 17:15:02
how do i scan the inputs when i don't know their count


Last edit: 2015-11-10 17:15:28
2015-09-29 17:18:58
Very nice one, got two WA for not using long long int .. finally AC :)
2015-09-28 04:05:41 shikhar jindal
plzz someone provide me with some tricky test cases..getting wa :(
2015-09-23 09:56:30 ASHUTOSH DWIVEDI


Last edit: 2015-09-25 18:23:34
2015-09-23 08:48:52 shantanu tripathi
nice :D
2015-09-22 21:05:40 ANIKET
#DAVID CAMPOO CAN YOU CHECK MY SUBMISSION (ID NO.15183898)
WHY IT IS GIVING WA?
CAN YOU TELL ME THE REASON


Last edit: 2015-09-23 10:29:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.