1/* ***********************************************
  2Author :111qqz
  3Created Time :2017年11月14日 星期二 20时22分15秒
  4File Name :G.cpp
  5************************************************ */
  6
  7#include <bits/stdc++.h>
  8#define PB push_back
  9#define fst first
 10#define sec second
 11#define lson l,m,rt<<1
 12#define rson m+1,r,rt<<1|1
 13#define ms(a,x) memset(a,x,sizeof(a))
 14typedef long long LL;
 15#define pi pair < int ,int >
 16#define MP make_pair
 17
 18using namespace std;
 19const double eps = 1E-8;
 20const int dx4[4]={1,0,0,-1};
 21const int dy4[4]={0,-1,1,0};
 22const int inf = 0x3f3f3f3f;
 23const int N=2E5+7;
 24struct PAM
 25{
 26    struct state
 27    {
 28    int fail,cnt,len;
 29    int nxt[26];
 30    }st[N];
 31    char S[N],RS[N];
 32    int n,now,sz;
 33    void init()
 34    {
 35    ms(st,0);
 36    st[0].fail = st[1].fail = 1;
 37    st[1].len = -1;
 38    sz = 1;
 39    }
 40    void extend(int c,int pos)
 41    {
 42    int p = now;
 43    while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
 44    if (!st[p].nxt[c]){
 45        int np=++sz,q=st[p].fail;
 46        st[np].len=st[p].len+2;
 47        while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
 48        st[np].fail=st[q].nxt[c];
 49        st[p].nxt[c] = np;
 50    }
 51    now=st[p].nxt[c];
 52    st[now].cnt++;
 53    }
 54    void Cnt()
 55    {
 56    for ( int i = sz ; i >= 2;  i--) st[st[i].fail].cnt += st[i].cnt;
 57    }
 58    void build ()
 59    {
 60    init();
 61    int len = strlen(S+1);
 62    for ( int i = 1 ; i <= len ; i++) extend(S[i]-'a',i);
 63    }
 64}A,B;
 65
 66LL ans;
 67void dfs( int x,int y)
 68{
 69  //  printf("x:%d y:%d\n",x,y);
 70    for ( int i = 0 ; i < 26 ; i++)
 71    {
 72    int u = A.st[x].nxt[i];
 73    int v = B.st[y].nxt[i];
 74    if (u&&v)
 75    {
 76        ans = ans + 1LL*A.st[u].cnt * B.st[v].cnt;
 77      //  printf("u:%d  v:%d ans:%lld\n",u,v,ans);
 78        dfs(u,v);
 79    }
 80    }
 81}
 82int main()
 83{
 84#ifndef  ONLINE_JUDGE
 85    freopen("./in.txt","r",stdin);
 86#endif
 87    int T,cas = 0 ;
 88    cin>>T;
 89    while (T--)
 90    {
 91    scanf("%s %s",A.S+1,B.S+1);
 92//  cout<<A.S<<"  "<<B.S<<endl;
 93    A.build();
 94    B.build();
 95    A.Cnt();
 96    B.Cnt();
 97    ans = 0 ;
 98    dfs(0,0) ;
 99    dfs(1,1) ; //奇偶起点
100    printf("Case #%d: %lld\n",++cas,ans);
101    }
102
103
104#ifndef ONLINE_JUDGE
105    fclose(stdin);
106#endif
107    return 0;
108}