#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int n;

ll ans;

ll pw(ll a,int b)

{

    ll ret=;

    for(;b;b>>=,a*=a)

        if(b&)ret*=a;

    return ret;

}

int gcd(int a,int b){return (a%b==)?b:gcd(b,a%b);}

ll rot(int n)

{

    ll ret=;

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

        ret+=pw(,gcd(i,n));

    return ret;

}

ll d(int n)

{

    if(n%)return (ll)n*pw(,(n-)/+);

    return (ll)n/*(pw(,n/)+(ll)pw(,(n-)/+));

}

int main()

{

    while()

    {

        scanf("%d",&n);

        if(!n)

        {

            printf("0\n"); continue;//!

        }

        if(n==-)return ;

        ans=(rot(n)+d(n))/(*n);

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

    }

}