#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 #define FILL(a,b) memset(a,b,sizeof(a))

 ll dp[][];

 int n;

 char str[];

 ll dfs(int l,int r)

 {

     if(dp[l][r]!=-)return dp[l][r];

     if(l>r)return dp[l][r]=;

     if(l==r)return dp[l][r]=;

     dp[l][r]=;

     if(str[l]==str[r])dp[l][r]+=dfs(l+,r-)+;

     dp[l][r]+=dfs(l+,r)+dfs(l,r-)-dfs(l+,r-);

     return dp[l][r];

 }

 int main()

 {

     int _case,t=;

     scanf("%d",&_case);

     while(_case--){

         scanf("%s",str);

         n=strlen(str);

         FILL(dp,-);

         printf("Case %d: %lld\n",t++,dfs(,n-));

     }

     return ;

 }