Description

DXM 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(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N.

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

Input

Input contains several test cases each with a number N per line.

Output

For each N, output a line ∑gcd(i, N) 1<=i <=N

Sample

Input

2
6

Output

3
15

Source: Limitfan