#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define MS0(a) memset(a,0,sizeof(a))

#define MS1(a) memset(a,-1,sizeof(a))

#define MSi(a) memset(a,0x3f,sizeof(a))

#define inf 0x3f3f3f3f

#define pb push_back

#define MK make_pair

#define A first

#define B second

#define eps 1e-8

#define zero(x) (((x)>0?(x):-(x))<eps)

#define bitnum(a) __builtin_popcount(a)

#define lowbit(x) (x&(-x))

#define clear0 (0xFFFFFFFE)

#define mod 1000000007

#define K(x) ((x)*(x))

typedef pair<int,int> PII;

typedef long long ll;

typedef unsigned long long ull;

template<typename T>

void read1(T &m)

{

    T x = ,f = ;char ch = getchar();

    while(ch <'' || ch >''){ if(ch == '-') f = -;ch=getchar(); }

    while(ch >= '' && ch <= ''){ x = x* + ch - '';ch = getchar(); }

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

template<typename T>

void out(T a)

{

    if(a>) out(a/);

    putchar(a%+'');

}

inline ll gcd(ll a,ll b){ return b == ? a: gcd(b,a%b); }

template<class T1, class T2> inline void gmax(T1& a, T2 b){ if(a < b) a = b;}

template<class T1, class T2> inline void gmin(T1& a, T2 b){ if(a > b) a = b;}

const int maxn = ;

int sa[maxn], t[maxn],t2[maxn],c[maxn],w[maxn];

int cmp(int *r,int a,int b,int l)

{

    return r[a] == r[b] && r[a+l] == r[b+l];

}

void build_sa(char *r,int n,int m)

{

    int i, j, p, *x = t, *y = t2;

    for(i = ; i < m;i++) c[i] = ;

    for(i = ; i < n;i++) c[x[i] = r[i]]++;

    for(i = ; i < m;i++) c[i] += c[i-];

    for(i = n-; i >= ; i--) sa[--c[x[i]]] = i;

    for(j = , p = ; p < n; j <<= , m = p){

        for(p = , i = n - j; i < n;i++) y[p++] = i;

        for(i = ; i < n; i++) if(sa[i] >= j) y[p++] = sa[i]-j;

        for(i = ; i < n; i++) w[i] = x[y[i]];

        for(i = ; i < m; i++) c[i] = ;

        for(i = ; i < n; i++) c[w[i]]++;

        for(i = ; i < m; i++) c[i] += c[i-];

        for(i = n-; i >= ; i--) sa[--c[w[i]]] = y[i];

        swap(x,y);

        for(p = , x[sa[]] = , i = ; i < n; i++)

            x[sa[i]] = cmp(y, sa[i-], sa[i], j)? p-: p++;

        if(p >= n) break;

        m = p;

    }

}

char S[maxn], X[maxn];

int  height[maxn], rk[maxn];

void getHeight(int n)

{

    for(int i = ; i<= n; i++) rk[sa[i]] = i;

    for(int i = , j, k = ; i < n; height[rk[i++]] = k)

        for(k? k--:, j = sa[rk[i] - ]; S[i+k] == S[j+k]; k++);

}

int f[maxn];

void getfail(char *p)

{

    f[] = f[] = ;

    int n = strlen(p);

    for(int i = ;i < n;i++){

        int j = f[i];

        if(j && p[i] != p[j]) j = f[j];

        f[i+] = (p[i] == p[j] ?j+:);// ｉ＋１会递推到第ｎ位

    }

}

vector<int> vec;

void Find(char *T, char *p)

{

    vec.clear();

    ll j = ,n = strlen(T),m = strlen(p);

    for(int i = ;i < n;i++){

        while(j && T[i] != p[j]) j = f[j];

        if(T[i] == p[j]) j++;

        if(j == m){

            vec.pb(i);

            j = ;

            i -= m-;

        }

    }

    sort(vec.begin(), vec.end());

}

int main()

{

    //freopen("data.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T, kase = ;

    scanf("%d",&T);

    while(T--){

        scanf("%s%s", X, S);

        int len = strlen(S), m = strlen(X);

        S[len] = '#';S[len+] = ;

        build_sa(S,len+,'z'+);

        getHeight(len);

        getfail(X);

        Find(S,X);

        vec.pb(len);

        ll ans = ;

        rep1(i,,len){

            if(sa[i]+m- > len) continue;

            int nxt = lower_bound(vec.begin(), vec.end(), sa[i]+m-) - vec.begin();

            ans += len - max(vec[nxt],sa[i] + height[i]);

        }

        printf("Case #%d: %lld\n", kase++, ans);

    }

    return ;

}