很裸的polya，不过我看polya看了很久

吉大ACM模板里面也有

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
long long gcd(long long a,long long b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
    #ifndef ONLINE_JUDGE
		//freopen("G:/1.txt","r",stdin);
		//freopen("G:/2.txt","w",stdout);
	#endif
	long long p[33];
	p[0]=1;
	for(long long i=1;i<=24;i++)
	{
		p[i]=p[i-1]*3;
		//cout<<p[i]<<endl;
	}
	long long res=0;
	long long s;
	while(cin>>s)
	{
        if(s==-1)
            break;
        if(s==0)
        {
            cout<<"0\n";
            continue;
        }
		long long res=s&1?s*p[s/2+1]:(s/2)*(p[s/2]+p[s/2+1]);
		for(long long k=1;k<=s;k++)
		{
			res+=p[gcd(k,s)];
		}
		res/=2*s;
		cout<<res<<'\n';
	}
    return 0;
}