#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ll long long

#define F(i,j,k) for (int i=j;i<=k;++i)

ll f[25],pow[30];

int n;

int gcd(int a,int b)

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

int main()

{

	f[0]=0;pow[0]=1;

	F(i,1,23) pow[i]=pow[i-1]*3;

	F(z,1,23)

	{

		F(i,0,z-1) f[z]+=pow[gcd(i,z)];

		if (z&1) f[z]+=z*pow[z/2+1];

		else f[z]+=z/2*pow[z/2],f[z]+=z/2*pow[z/2+1];

		f[z]/=2*z;

	}

	while (scanf("%d",&n)&&n>=0)

		printf("%lld\n",f[n]);

}