Longge's problem

Time Limit: 1000MS

Memory Limit: 65536K

[显示标签]

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(1 < N < 2^31),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

Sample Input

2
6

Sample Output

3
15

Hint

Source

POJ Contest,Author:Mathematica@ZSU

提交代码