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
dubeyankur016: 2020-01-20 03:46:38

use scanf , printf and while(scanf("%lld",&n)!=EOF) for input numbers AC

priyanshucode: 2019-10-10 21:46:40

image link -> https://vj.z180.cn/0dfe6853f57754cccad8cfa7dbd889eb?v=1570280352

rohit9934: 2017-05-04 15:49:22

what kind of sorcery is this, WA without EOF.

stormborn7777: 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

eccentric_geek: 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
dwij28: 2015-09-29 17:18:58

Very nice one, got two WA for not using long long int .. finally AC :)

shikhar jindal: 2015-09-28 04:05:41

plzz someone provide me with some tricky test cases..getting wa :(

ASHUTOSH DWIVEDI: 2015-09-23 09:56:30

Last edit: 2015-09-25 18:23:34
shantanu tripathi: 2015-09-23 08:48:52

nice :D

ANIKET: 2015-09-22 21:05:40

#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

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