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

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

Input contain several test case. 
A number N per line. 

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

2

6

3

15
翻译：给一个数n,1<=i<=n,求gcd(i,n)之和。
解题过程：
令d=gcd(i,n)，d必然是n的因子，并且是i和n的最大公因子。
则gcd(i/d,n/d)=1。令y=n/d,通过y求出与y互质的数的个数，然后对这个数量乘以最大公因子d，累加。

 #include <iostream>

 #include<stdio.h>

 #include <algorithm>

 #include<string.h>

 #include<cstring>

 #include<math.h>

 #define inf 0x3f3f3f3f

 #define ll long long

 using namespace std;

 ll euler(ll x)

 {

     ll res=x;

     for(ll i=;i*i<=x;i++)

     {

         if(x%i==)

         {

             res=res/i*(i-);

             while(x%i==)

                x=x/i;

         }

     }

     if(x>)

         res=res/x*(x-);

     return res;

 }

 int main()

 {

     ll n,sum;

     while(scanf("%lld",&n)!=EOF)

     {

         sum=;

         ll i;

         for(i=;i*i<=n;i++)

         {

             if(n%i==)

                 sum+=i*euler(n/i)+(n/i)*euler(i);

         }

         i--;

         if(i*i==n)

             sum-=i*euler(i);

         printf("%lld\n",sum);

     }

     return ;

 }