Longge`s 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$. Compute $\sum gcd(i,n)$ for all $1\le i\le n$.

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

Input

Each line contains one number $n(1<n<2^{31})$.

Output

For each number $n$ print in a separate line the sum $\sum gcd(i,n)$ for all $1\le i\le n$.

Examples