C++ :

#include <cstdio>
using namespace std;
typedef long long LL;
bool bp[10000001];
int p[664580], cnt;
int f[664580], l;
int bf[200], num[200], bcnt;
void getp()
{
    for (int i=2; i<10000001; i++)
    {
        if (bp[i] == 0) p[cnt++] = i;
        for (int j=0; j<cnt; j++)
        {
            LL t;
            if ((t=p[j]*i)>10000000) break;
            bp[t] = 1;
            if (i%p[j] == 0) break;
        }
    }
}

LL mod_mult ( LL a, LL b, LL n )
{
    LL ret = 0;
    a = a % n;b = b % n;
    while ( b >= 1 )
    {
        if ( b & 1 )
        {
            ret += a;
            if ( ret >= n ) ret -= n;
        }
        a = a << 1;
        if ( a >= n ) a -= n;
        b = b >> 1;
    }
    return ret;
}

LL mod_exp ( LL a, LL b, LL n )
{
    LL ret = 1;
    a = a % n;
    if (b==1) return a;
    while ( b >= 1 )
    {
        if ( b & 1 )
           ret =  mod_mult(ret,a,n);
        a = mod_mult(a,a,n);
        b = b >> 1;
    }
    return ret;
}

int main()
{
    //freopen("1.txt", "r", stdin);
    getp();
    int N, B, T, ci=0;
    scanf ("%d", &T);
    while (T--)
    {
        scanf ("%d%d", &N, &B);
        if (!bp[B])
        {
            int base[B+1];base[0] = 1;
            for (int i=0; i<B; i++) base[i+1] = base[i] * (i+1) % B;
            int ans = base[N%B];
            for (int t=N/B; t>0; t/=B)
            {
                ans = ans*mod_exp(B-1, t%(B-1), B)%B;
                ans = base[t%B]*ans%B;
            }
            printf ("Case #%d: ", ++ci);
            printf ("%d\n", (int)ans);
            continue;
        }
        int phi = B;
        for (l=0; l<cnt; l++)
        {
            if (N<p[l]) break;
            f[l] = 0;
            int n = N;
            while (n)
            {
                n /= p[l];
                f[l] += n;
            }
        }
        bcnt = 0;int b = B;LL minn = 0x7FFFFFFF;
        for (int i=0; i<cnt; i++)
        {
            if (b==1)break;
            if (b%p[i] == 0)
            {
                bf[bcnt] = i;
                phi -= phi/p[i];
                num[bcnt] = 0;
                while (b%p[i]==0)
                {
                    num[bcnt]++;
                    b /= p[i];
                }
                int t = f[bf[bcnt]]/num[bcnt];
                if (t<minn) minn = t;
                bcnt++;
            }
        }
        for (int i=0; i<bcnt; i++)
        {
            f[bf[i]] -= num[i]*minn;
        }
        LL ans = 1;
        for (int i=0; i<l; i++)
        {
            int t = mod_exp(p[i], f[i]%phi, B);
            ans = mod_mult(ans, t, B);
        }
        printf ("Case #%d: ", ++ci);
        printf ("%d\n", (int)ans);
    }
    return 0;
}