#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

typedef  long long  ll;

typedef unsigned long long ull;

#define MM(a,b) memset(a,b,sizeof(a));

#define inf 0x7f7f7f7f

#define FOR(i,n) for(int i=1;i<=n;i++)

#define CT continue;

#define PF printf

#define SC scanf

const int mod=1000000007;

const int N=1e5+10;

int la,lb;

ll dp[N];

char a[N],b[N];

ull ha[N],hb;

ull seed=13331;

void init(){

   hb=0;

   for(int i=0;i<lb;i++)

       hb=hb*seed+b[i];

   ull base=1;

   for(int i=1;i<=lb-1;i++) base*=seed;

   ha[0]=a[0];

   for(int i=1;i<=lb-1;i++)

       ha[i]=ha[i-1]*seed+a[i];

   for(int i=lb;i<la;i++)

       ha[i]=(ha[i-1]-a[i-1-(lb-1)]*base)*seed+a[i];

}

int main()

{

    int cas,kk=0;

    scanf("%d",&cas);

    while(cas--){

        scanf("%s",a);

        scanf("%s",b);

        la=strlen(a);lb=strlen(b);

        if(la<lb) {printf("Case #%d: 1\n",++kk);CT;}

        init();

        for(int i=0;i<=lb-1;i++) dp[i]=1;

        if(ha[lb-1]==hb) dp[lb-1]=2;

        for(int i=lb;i<la;i++){

           dp[i]=dp[i-1]%mod;

           if(ha[i]==hb) dp[i]=(dp[i]+dp[i-lb])%mod;

        }

        printf("Case #%d: %lld\n",++kk,dp[la-1]%mod);

    }

    return 0;

}