Competitions

# Longges problem

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 (1n231), you are to calculate ∑gcd(i,n) for all 1in.

"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.

#### Input

Each line contains one number n.

#### Output

For each number n print in a separate line ∑gcd(i, n) for all 1in.

Time limit 1 second
Memory limit 64 MiB
Input example #1
2
6
12

Output example #1
3
15
40
`