d.cpp

#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

#ifdef DEBUG
#define dbg(msg) msg
#define dbgp(msg) cerr << msg << endl;
#define var(v) cerr << #v << " = " << v << endl;
#else
#define dbg(msg) //msg
#define dbgp(msg) //cerr << msg << endl;
#define var(v) //cerr << #v << " = " << v << endl;
#endif

#define MOD 1000000003

ll dp[1010][1010];

ll solve(){
    string s1;
    string s2;
    cin >> s1 >> s2;

    // Just debugging
    var(s1);
    var(s1.size());
    var(s2);
    var(s2.size());

    // Clear to 0
    memset(dp, 0, sizeof dp);

    // Two loop
    REP(i,s1.size()){
        REP(i2,s2.size()){

            if(i == 0){

                // If on boundary but not on 0,0, use neighbour value as initial value
                if(i2 == 0){
                }else{
                    dp[i][i2] = dp[i][i2-1];
                }

                // If the character is the same, add one more subsequence
                if(s1[i] == s2[i2]){
                    dp[i][i2] += 1;
                }
                dp[i][i2] %= MOD;

            }else if(i2 == 0){

                // Same thing as previous one, but different side
                if(i == 0){
                }else{
                    dp[i][i2] = dp[i-1][i2];
                }

                if(s1[i] == s2[i2]){
                    dp[i][i2] += 1;
                }
                dp[i][i2] %= MOD;

            }else{

                if(s1[i] == s2[i2]){
                    // If the character is the same,
                    // Add another subsequence
                    // And the number of subsequence onf i-1 and i2-1
                    // But since we are going to subtract it anyway, we just skip the subtraction
                    dp[i][i2] += 1;

                    // Count from above and side is added
                    dp[i][i2] %= MOD;
                    dp[i][i2] += dp[i-1][i2];
                    dp[i][i2] %= MOD;
                    dp[i][i2] += dp[i][i2-1];
                    dp[i][i2] %= MOD;

                    // Skip subtraction
                    //dp[i][i2] = MOD+dp[i][i2]-dp[i-1][i2-1];
                    //dp[i][i2] %= MOD;

                }else{
                    // If the character is not the same,
                    // We add the number of subsequence above and on size
                    // But because both of them contain the number of subsequence from the diagonal i-1 and i2-1,
                    // We need to remove minus that.
                    // Remember the formula |A union B| = |A| + |B| - |A intersect B|

                    dp[i][i2] += dp[i-1][i2];
                    dp[i][i2] %= MOD;
                    dp[i][i2] += dp[i][i2-1];
                    dp[i][i2] %= MOD;

                    dp[i][i2] = MOD+dp[i][i2]-dp[i-1][i2-1];
                    dp[i][i2] %= MOD;
                }
            }

        }
    }

    // Just debugging
    dbg(
    REP(i,s1.size()){
        REP(i2,s2.size()){
            cerr << dp[i][i2] << " ";
        }
        cerr << endl;
    }
    )

    return (dp[s1.size()-1][s2.size()-1]+1)%MOD;
}

int main(int argv, char** argc){
    cin.sync_with_stdio(0);

    int t = INT_MAX;
    cin >> t;
    REP(i,t){
        printf("Case #%lld: %lld\n",i+1,solve());
    }

    return 0;
}