#include<iostream>

#include<stdio.h>

#include <algorithm>

#include <string>

#include<string.h>

#include<math.h>

#define  ll long long

using namespace std;

const int MAXN =  ;

const int N =  ;

char s[MAXN],ss[MAXN];//输入的要处理的字符串

ll ans=;

struct Palindromic_Tree

{

     int next[MAXN][] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成

     int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点

     //回文树里面的一个节点就代表一个回文串

     int cnt[MAXN] ;//表示第i个节点代表的回文串出现的次数

     int num[MAXN] ; //表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。

     int len[MAXN] ;//表示第i个节点代表的回文串长度

     int S[MAXN] ;//存放添加的字符

     int last ;//指向上一个字符所在的节点，方便下一次add

     int n ;//字符数组指针

     int p ;//节点指针

     int newnode(int l)     //在树中新建节点

     {

           for(int i =  ; i < N ; ++ 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)     //和KMP一样，失配后找一个尽量最长的

     {

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

              x = fail[x] ;

          return x ;

     }

     void add(int c,int pos)

     {

           //printf("%d:",p);//------------>输出节点编号,第一个有回文串的编号时从2开始

           c -= 'a';

           S[++ n] = c ;

           int cur = get_fail(last) ;   //通过上一个回文串找这个回文串的匹配位置

           //printf("%d ",cur);//输出节点编号p代表的回文串的字符长度

           if(!next[cur][c])     //如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串

           {

                 int now = newnode(len[cur] + ) ;   //新建节点

                 fail[now] = next[get_fail(fail[cur])][c] ;   //和AC自动机一样建立fail指针，以便失配后跳转

                 next[cur][c] = now ;

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

                 //for(int i=pos-len[now]+1; i<=pos; ++i)//--------->输出编号为P代表的回文串

                 //   printf("%c",s[i]);

           }

           last = next[cur][c] ;

           cnt[last] ++ ;

           //putchar(10);//------------->输出回车换行

     }

     void count()

     {

           for(int i = p -  ; i >=  ; -- i)

                cnt[fail[i]] += cnt[i] ;

           //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！

     }

} pat1,pat2;

void dfs(int x,int y)

{

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

    {

        //son1、son2是节点编号

        int son1=pat1.next[x][i];

        int son2=pat2.next[y][i];

        //cout<<son1<<" "<<son2<<endl;

        if(son1&&son2)

        {

            ans=ans+(ll)pat1.cnt[son1]*pat2.cnt[son2];//ans记录有多少对本质不同的字符串子序列

            dfs(son1,son2);

        }

    }

}

int main()

{

    int t,k=;

    scanf("%d",&t);

    while(t--)

    {

        ans=;

        scanf("%s",s);

        int n=strlen(s);

        pat1.init();

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

            pat1.add(s[i],i);

        pat1.count();

        scanf("%s",&ss);

        int nn=strlen(ss);

        pat2.init();

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

            pat2.add(ss[i],i);

        pat2.count();

        dfs(,);//遍历长度为偶数的回文树

        dfs(,);//遍历长度为奇数的回文树

        printf("Case #%d: ",k++);

        printf("%lld\n",ans);

    }

    return ;

}

/*

3

abacab

abccab

faultydogeuniversity

hasnopalindromeatall

abbacabbaccab

youmayexpectedstrongsamplesbutnow

*/