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$. Compute $∑gcd(i, n)$ for all $1 \le i \le n$. "Oh, I know, I know!" Longge shouts! But do you know? Please solve it. \InputFile Each line contains one number $n~(1 < n < 2^{31})$. \OutputFile For each number $n$ print in a separate line the sum $∑gcd(i, n)$ for all $1 \le i \le n$.