/* ***********************************************

Author        :guanjun

Created Time  :2016/6/30 23:24:27

File Name     :1025.cpp

************************************************ */

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <iomanip>

#include <list>

#include <deque>

#include <stack>

#define ull unsigned long long

#define ll long long

#define mod 90001

#define INF 0x3f3f3f3f

#define maxn 10010

#define cle(a) memset(a,0,sizeof(a))

const ull inf = 1LL << ;

const double eps=1e-;

using namespace std;

priority_queue<int,vector<int>,greater<int> >pq;

struct Node{

    int x,y;

};

struct cmp{

    bool operator()(Node a,Node b){

        if(a.x==b.x) return a.y> b.y;

        return a.x>b.x;

    }

};

bool cmp(int a,int b){

    return a>b;

}

ll dp[][];

char s[];

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

    //freopen("out.txt","w",stdout);

    int T;

    cin>>T;

    for(int t=;t<=T;t++){

        scanf("%s",s+);

        int n=strlen(s+);

        cle(dp);

        for(int len=;len<=n;len++){

            for(int i=;i+len-<=n;i++){

                int j=i+len-;

                dp[i][j]+=dp[i+][j]+dp[i][j-]-dp[i+][j-];

                if(s[i]==s[j])dp[i][j]+=dp[i+][j-]+;

            }

        }

        printf("Case %d: %lld\n",t,dp[][n]);

    }

    return ;

}