Description
Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms.
Now a problem comes: Given an integer N,you are to calculate ∑gcd(i, N) 1<=i <=N.
"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.
Input
Input contain several test case.
A number N per line.
Output
For each N, output ,∑gcd(i, N) 1<=i <=N, a line
HINT
-
对于 60% 的数据，保证 n≤216。
-
对于 100% 的数据，保证 1≤n<232。