# Longge`s problem

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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≤i≤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 $∑gcd(i,n)$ for all $1≤i≤n$.

## Examples

Input #1

Answer #1

Submissions 3K

Acceptance rate 28%