#include <iostream>#include <math.h>using namespace std;#define LL long longLL gcd(LL a, LL b){    return b ? gcd(b, a % b) : a;}LL polya(LL n){    LL ret = 0;    for(LL i = 0; i < n; i++)        ret += pow(3, gcd(i, n));    //flip them...    if( n & 1 )//odd        ret += n * pow(3, n / 2 + 1);//symmetric axis‘s num is n, and a cycle of (n + 1) / 2, with the length of 2, and 2 cycles with length of 1...      else//even      ret += n / 2 * pow(3, n / 2) + (n / 2) * pow(3, n / 2 + 1);//symmetric axis‘s num is n, categoried by the beeds, for n/2 axis which through the beed, they formed (n/2-1) cycles with the length of 2, and 2 cycles with the length of 1; for the n/2 axis which not through the beed, they formed (n/2) cycles with the length of 2.    else//even   ret += n / 2 * pow(3, n / 2) + (n / 2) * pow(3, n / 2 + 1);//    return ret / n / 2;//the average of them(according to Polya Theorem.)}int main(){    LL n;    while(cin>> n && n != -1)    {        if (n <= 0) cout << 0 << endl;        else cout << polya(n) << endl;    }    return 0;}

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>using namespace std;#define n 3__int64 m;int gcd(int a, int b){    b = b % a;    while (b)    {        a = a % b;        swap(a, b);    }    return a;}int main(){    while (scanf("%lld", &m)!=EOF)    {        if(m==-1)        break;        __int64 ans = 0;        for (int i = 1; i <= m; i++)            ans += pow(n*1.0, gcd(i, m)*1.0);        if (m & 1)            ans += m * pow(n*1.0, (m / 2 + 1)*1.0);        else            ans += m / 2 * pow(n*1.0, (m / 2)*1.0) + m / 2 * pow(n*1.0, (m / 2 + 1)*1.0);        ans /= m * 2;        printf("%I64d\n", ans);    }    return 0;}