Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

一个整数，为N。

一个整数，为所求的答案。

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

typedef long long ll;

const int maxn=1010;

ll pri[maxn],ans[maxn],res,n;

int cnt;

int main() {

	scanf("%lld",&n);

	for(ll i=1;i*i<=n;i++) if(n%i==0) {

		pri[++cnt]=i;

		if(i*i!=n) pri[++cnt]=n/i;

	}

	sort(pri+1,pri+cnt+1);

	dwn(i,cnt,1) {

		ans[i]=n/pri[i];

		rep(j,i+1,cnt) if(pri[j]%pri[i]==0) ans[i]-=ans[j];

	}

	rep(i,1,cnt) res+=ans[i]*pri[i];

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

	return 0;

}