#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define LL __int64

using namespace std;

LL Power(int a,int b){

	LL ret=1; LL p=(LL)a;

	while(b){

		if(b&1) ret=ret*p;

		p=p*p;

		b>>=1;

	}

	return ret;

}

LL Euler(int s){

	LL ret=(LL)s;

	int l=(int)sqrt(s*1.0);

	for(int i=2;i<=l;i++){

		if(s%i==0){

			ret=ret-ret/(LL)i;

			while(s%i==0)

			s/=i;

		}

	}

	if(s>1)

	ret=ret-ret/s;

	return ret;

}

LL Burnside(int n){

	LL res=0;

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

		if(n%i==0)

		res=res+Power(3,i)*Euler(n/i);

	}

	if(n&1){

		res=res+n*Power(3,n/2+1);

	}

	else{

		res=res+n/2*Power(3,n/2)+n/2*Power(3,n/2+1);

	}

	return res;

}

int main(){

	int n;

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

		if(n==-1) break;

		if(n==0) printf("0\n");

		else{

			LL ans=Burnside(n);

			ans=ans/2/n;

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

		}

	}

	return 0;

}