eolymp
bolt
Try our new interface for solving problems
Problems

Longge`s problem

Longge`s problem

Time limit 1 second
Memory limit 128 MiB

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.

Input data

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

Output data

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

Examples

Input example #1
2
6
12
Output example #1
3
15
40