/*  * hdu3923.c  *  *  Created on: 2011-9-20  *      Author: bjfuwangzhu */ #include
     
       #include
      
        #define LL long long #define nnum 1000000007 LL x, y; LL modular_exp(int a, int b) {
       LL res, temp;     res = 1 % nnum,temp = a % nnum; while (b) {
   if (b & 1) {
               res = res * temp % nnum;         }         temp = temp * temp % nnum;         b >>= 1;     } return res; } int getPhi(int n) {
   int phi, i, te;     te = (int) (sqrt(n * 1.0)); for (i = 2, phi = n; i <= te; i++) {
   if (n % i == 0) {
               phi = phi / i * (i - 1); while (n % i == 0) {
                   n /= i;             }         }     } if (n > 1) {
           phi = phi / n * (n - 1);     } return phi; } void extend_gcd(int a, int b) {
   if (b == 0) {
           x = 1LL, y = 0; return;     }     extend_gcd(b, a % b);     LL tx = x;     x = y, y = tx - a / b * y; } LL polya(int n, int m) {
   int i;     LL sum; for (i = 1, sum = 0; i <= m; i++) {
   if (m % i == 0) {
               sum += modular_exp(n, i) * getPhi(m / i) % nnum;             sum %= nnum;         }     } if (m & 1) {
           sum += modular_exp(n, (m + 1) / 2) * m % nnum;         sum %= nnum;     } else {
           sum += modular_exp(n, m / 2) * (m / 2) % nnum;         sum %= nnum;         sum += modular_exp(n, m / 2 + 1) * (m / 2) % nnum;         sum %= nnum;     }     extend_gcd(m << 1, nnum);     x = (x % nnum + nnum) % nnum;     sum = sum * x % nnum; return sum; } int main() {
   #ifndef ONLINE_JUDGE     freopen("data.in", "r", stdin); #endif int i, t, n, m;     LL sum; while (~scanf("%d", &t)) {
   for (i = 1; i <= t; i++) {
               scanf("%d %d", &n, &m);             sum = polya(n, m);             printf("Case #%d: %I64d\n", i, sum);         }     } return 0; }