#include<string.h>

#include<algorithm>

#include<stdio.h>

using namespace std;

long long quick_pow(long long a,long long b){

    long long rel=;

    while(b){

        if(b&)rel*=a;

        a=a*a;

        b>>=;

    }

    return rel;

}

int gcd(int a,int b){

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

}

int main()

{

    int n;

    scanf("%d",&n);

    while(n>=){

        if(n==){printf("0\n");scanf("%d",&n);continue;}

        long long ans=;

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

            ans+=quick_pow(,gcd(n,i));

        }

        if(n&){

            ans+=n*quick_pow(,n/+);

        }

        else{

            ans+=n/*quick_pow(,n/+);

            ans+=n/*quick_pow(,n/);

        }

        printf("%I64d\n",ans/n/);

        scanf("%d",&n);

    }

}