#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e6 + 2;

const LL MOD = 1000003;

LL Pow_Mod(LL a, LL n)

{

    LL ret = 1;

    while(n)

    {

        if(n & 1) ret = ret * a % MOD;

        n >>=1;

        a = a * a % MOD;

    }

    return ret;

}

LL Num[maxn], Inv[maxn];

LL Init()

{

    Num[0] = 1;

    for(LL i = 1; i < maxn; ++i) Num[i] = Num[i-1] * i % MOD;

    //cout << Num[maxn-1] << endl;

    Inv[maxn-1] = Pow_Mod(Num[maxn-1], MOD-2);

    for(LL i = maxn-2; i >= 0; --i)

        Inv[i] = Inv[i+1] * (i+1) % MOD;

}

LL C(LL m, LL n)

{

    LL ret = 1;

    if(n == 0 || n == m) return ret;

    else

    {

        LL s = m-n;

        //cout << s << endl;

        ret = Num[m] * Inv[s] % MOD;

        //cout << Num[m] << "   " << Inv[s] << endl;

        ret = ret * Inv[n] % MOD;

        //cout << Inv[n] << endl;

        return ret;

    }

}

int main()

{

    Init();

    int t;

    LL m, n;

    scanf("%d",&t);

    for(int kase = 1; kase <= t; ++kase)

    {

        scanf("%lld %lld",&m,&n)    ;

        printf("Case %d: %lld\n",kase, C(m,n));

    }

}