#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + ;

const int mod = ;

long long dp[maxn];

char str1[maxn], str2[maxn];

bool flag[maxn];

/*

* nex[] 的含义:x[i-nex[i]...i-1]=x[0...nex[i]-1]

* nex[i] 为满足 x[i-z...i-1]=x[0...z-1] 的最大 z 值(就是 x 的自身匹配)

*/

void kmp_pre(char x[], int m, int kmpNext[]) {

    int i, j;

    j = kmpNext[] = - ;

    i = ;

    while(i < m) {

        while( -  != j && x[i] != x[j])

            j = kmpNext[j];

        kmpNext[++i] = ++j;

    }

}

/*

* kmpNext[i] 的意思:nex'[i]=nex[nex[...[nex[i]]]](直到

nex'[i]<0 或者 x[nex'[i]]!=x[i])

* 这样的预处理可以快一些

*/

void preKMP(char x[], int m, int kmpNext[]) {

    int i, j;

    j = kmpNext[] = - ;

    i = ;

    while(i < m) {

        while( -  != j && x[i] != x[j])

            j = kmpNext[j];

        if(x[++i] == x[++j])

            kmpNext[i] = kmpNext[j];

        else

            kmpNext[i] = j;

    }

}

/*

* 返回 x 在 y 中出现的次数,可以重叠

*/

int nex[];

int KMP_Count(char x[], int m, char y[], int n) { //x 是模式串,y 是主串

    int i, j;

    int ans = ;

//preKMP(x,m,nex);

    kmp_pre(x, m, nex);

    i = j = ;

    while(i < n) {

        while( -  != j && y[i] != x[j])

            j = nex[j];

        i++;

        j++;

        if(j >= m) {

            ans++;

            flag[i] = ;

            j = nex[j];

        }

    }

    return ans;

}

int main() {

    int T, ncase = ;

    scanf("%d", &T);

    while(T --) {

        scanf("%s%s", str1, str2);

        int l1 = strlen(str1);

        int l2 = strlen(str2);

        memset(flag, , sizeof(flag));

        memset(dp, , sizeof(dp));

        KMP_Count(str2, l2, str1, l1);

        for(int i = l2; i <= l1; i ++)

            dp[i] = flag[i] ? (dp[i - ] + dp[i - l2] + ) % mod : dp[i - ];

        printf("Case #%d: %lld\n",ncase++,(dp[l1] + )%mod);

    }

    return ;

}