/*--------------------------------------------------------------------------------------*/

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <ctype.h>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <string>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <map>

 //debug function for a N*M array

 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\

 {for(int j=;j<(M);j++){\

 printf("%d",G[i][j]);}printf("\n");}

 //debug function for int,float,double,etc.

 #define debug_var(X) cout<<#X"="<<X<<endl;

 #define LL long long

 const int INF = 0x3f3f3f3f;

 const LL LLINF = 0x3f3f3f3f3f3f3f3f;

 /*--------------------------------------------------------------------------------------*/

 using namespace std;

 int N,M,T;

 const LL MOD = 1e9+;

 LL pow_mod(LL x,LL cnt)

 {

     LL base = x,res = ;

     while(cnt)

     {

         if(cnt&) {res*=base;res%=MOD;}

         base *= base;base %= MOD;

         cnt >>= ;

     }

     return res%MOD;

 }

 LL inv(LL x,LL m)

 {

     return pow_mod(x,m-);

 }

 LL polya(LL n,LL m)

 {

     LL res = ;

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

     {

         res += pow_mod(m,__gcd((LL)i,n));

         res %= MOD;

     }

     if(n&) res += n*pow_mod(m,n/+);

     else res += (n*pow_mod(m,n/))%MOD*inv(,MOD)%MOD + (n*pow_mod(m,n/+))%MOD*inv(,MOD)%MOD ;

     res %= MOD;

     res *= inv(*n,MOD);

     return res%MOD;

 }

 int main()

 {

     scanf("%d",&T);

     int cas = ;

     while(T--)

     {

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

         printf("Case #%d: %lld\n",++cas,polya(N,M));

     }

 }