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 ≤
231), you are to calculate ∑gcd(i,n) for all 1 ≤ i ≤ n.
"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.
Each line contains one number n.
For each number n print in a separate line ∑gcd(i, n) for all 1 ≤ i ≤ n.
2 6 12
3 15 40