/*
* hdu3923.c
*
* Created on: 2011-9-20
* Author: bjfuwangzhu
*/
#include<stdio.h>
#include<math.h>
#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;
}