#include <bits/stdc++.h>
/*
WAY TO CANDIDATE MASTER
*/
using namespace std;
typedef long long ll;
typedef long double ld;

const int MX=5e5+3;
string h;
ll dp[66][66];
ll solve(int r,int l)
{
    ll ans=0;
    if(dp[r][l]!=-1)return dp[r][l];
     if(h[r]==h[l])
        ans++;
     else return 0;
    for(int i=0;i<r;i++)
    {
        for(int k=l+1;k<h.length();k++)
        {
            ans+=solve(i,k);
        }
    }
    return dp[r][l]=ans;
}
char bb[66];
int main()
{
   // freopen("aa.txt","r",stdin);
   //  freopen("aa.txt","w",stdout);
    /*for(int i=0;i<200;i++)
    {
        for(int k=0;k<60;k++)
            cout<<'a';
        cout<<endl;
    }

    return 0;*/
    int t;
    cin>>t;
    int g=0;
    while(t--){

    memset(dp,-1,sizeof dp);
    scanf("%s",bb);
    h=bb;


    g++;
    ll ans=0;
    for(int i=0;i<h.length();i++)
         for(int k=i;k<h.length();k++)
            ans+=solve(i,k);
        printf("Case %d: %I64d\n",g,ans);
    }
    return 0;
}