#include <iostream>

#include <algorithm>

#include <string.h>

#include <vector>

#include <cstdio>

using namespace std;

const int maxn=;

const int sign_size=;

struct Palind_Tree{

 int next[maxn][sign_size];

 int fail[maxn];

 int cnt[maxn];

 int num[maxn];

 int len[maxn];

 int S[maxn];

 int last;

 int n;

 int p;

 int newnode(int l)

 {

     for(int i=; i<sign_size; i++)next[p][i]=;

     cnt[p]=;

     num[p]=;

     len[p]=l;

     return p++;

 }

 void init()

 {

     p=;

     newnode();

     newnode(-);

     last=;

     n=;

     S[n]=-;

     fail[]=;

 }

 int get_fail(int x)

 {

    while(S[n-len[x]-]!=S[n])x=fail[x];

    return x;

 }

 void add(int c)

 {

     c-='a';

     S[++n]=c;

     int cur=get_fail(last);

     if(next[cur][c]==)

     {

         int now=newnode(len[cur]+);

         fail[now]=next[get_fail( fail[cur] )][c];

         next[cur][c]=now;

         num[now]=num[fail[now]]+;

     }

     last=next[cur][c];

     cnt[last]++;

 }

 void count()

 {

     for(int i=p-; i>=; --i)cnt[fail[i]]+=cnt[i];

 }

}T1,T2;

char S[maxn],S2[maxn];

long long ans=;

void dfs(int u,int v)

{

    for(int i=; i<sign_size; i++)

    {

        int x=T1.next[u][i],y=T2.next[v][i];

        if(x&&y)

        {

            ans+=(long long)T1.cnt[x]*T2.cnt[y];

            dfs(x,y);

        }

    }

}

int main()

{

    int cas;

    scanf("%d",&cas);

    for(int cc=; cc<=cas; cc++)

    {

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

        T1.init();

        T2.init();

        int len1=strlen(S);

        int len2=strlen(S2);

        for(int i=; i<len1; i++)

            T1.add(S[i]);

        for(int i=; i<len2; i++)

            T2.add(S2[i]);

        T1.count();

        T2.count();

        ans=;

        dfs(,);

        dfs(,);

        printf("Case #%d: %I64d\n",cc,ans);

    }

    return ;

}