#include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 LL P_M( LL a, LL b )

 {

     LL res=, t=a;

     while (b){

         if(b&)res*=t;

         t*=t;

         b>>=;

     }

     return res;

 }

 int a[], vi[];

 void dfs( int i )

 {

     if( !vi[i] ){

         vi[i]=;

         dfs(a[i]);

     }

 }

 int find(int t, int n ) // 求循环节 s == gcd( n, t ) ;

 {

     memset(vi, , sizeof vi);

     memset(a, , sizeof a);

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

         int e=(i+t-)%n;

         if( e== )e=n;

         a[i]=e;

     }

     int s=;

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

         if(!vi[i]){

             dfs(i);

             s++;

         }

     }

     return s;

 }

 int gcd( int x, int y )

 {

     return y==?x:gcd( y, x%y );

 }

 int main( )

 {

     int N;

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

         if( N==- )break;

         if( N== ){puts(""); continue;}

         LL ans=;

         if( !(N&) ){

             ans=P_M(3LL, N);

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

                 int t=find(i, N);

                 ans+=P_M( 3LL,t );

             }

             ans+=(LL)(N/)*(P_M(3LL,(N+)/));

             ans+=(LL)(N/)*P_M(3LL,N/);

         }

         else{

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

                ans+=P_M(3LL, gcd(i, N));

             }

             ans+=(LL)(N)*(P_M(3LL,N/+));

         }

         printf( "%d\n", ans/(*N) );

     }

     return ;

 }

 #include <cstdio>

 #include <iostream>

 using namespace std;

 int N, M;

 typedef long long LL;

 LL P_M(int a, int b )

 {

     LL res=,t=a;

     while(b){

         if(b&)res*=t;

         t*=t;

         b>>=;

     }

     return res;

 }

 int gcd( int x, int y )

 {

     return y==?x:gcd( y, x%y );

 }

 LL polya( int k, int m )

 {

     LL ans=;

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

         ans+=P_M(k, gcd( i, m ));

     }

     if( m& ){

         ans+=(LL)(m*P_M( k, m/+ ) );

     }

     else {

         ans+=(LL)m/*P_M(k, m/);

         ans+=(LL)m/*P_M(k, m/+);

     }

     if(m)ans/=,ans/=m;

     return ans;

 }

 int main( )

 {

     while(scanf("%d%d", &N,&M)!=EOF, N+M ){

         printf("%lld\n", polya(N, M));

     }

     return ;

 }

 #include <cstdio>

 #include <iostream>

 using namespace std;

 typedef long long LL;

 const LL M=1e9+;

 LL P_M(int a, int b )

 {

     LL res=,t=a;

     while(b){

         if(b&)res*=t, res%=M;

         t*=t, t%=M;

         b>>=;

     }

     return res;

 }

 int gcd( int x, int y )

 {

     return y==?x:gcd( y, x%y );

 }

 LL polya( int k, int m )

 {

     LL ans=;

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

         ans+=P_M(k, gcd( i, m ));

         ans%=M;

     }

     if( m& ){

         ans+=(LL)(m*P_M( k, m/+ ) );

     }

     else {

         ans+=(LL)m/*P_M(k, m/);

         ans+=(LL)m/*P_M(k, m/+);

     }

     ans%=M;

     return   (ans*P_M(*m,M-))%M;// 求逆元

 }

 int main( )

 {

     int T, N, K, t=;

     scanf("%d", &T);

     while(T--){

         scanf("%d%d", &N,&K);

         printf("Case #%d: %I64d\n", t++, polya(N, K));

     }

     return ;

 }