//不同回文子串数目

#include <iostream>

#include <string>

#include <cmath>

#include <map>

using namespace std;

#define N 200010

int ws1[N],wv[N],wa[N],wb[N];

int rank1[N],height[N],sa[N];

char str[N];

int a[N],n;

int dp[N][],vis[N];

int mmin(int a,int b)

{

    return a>b?b:a;

}

int cmp(int *r,int a,int b,int l)

{

    return r[a]==r[b] && r[a+l]==r[b+l];

}

void da(int *r,int *sa,int n,int m)

{

    int i,j,p,*x=wa,*y=wb,*t;

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

        ws1[i]=;

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

        ws1[x[i]=r[i]]++;

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

        ws1[i]+=ws1[i-];

    for(i=n-;i>=;i--)

        sa[--ws1[x[i]]]=i;

    for(j=,p=;p<n;j*=,m=p)

    {

        for(p=,i=n-j;i<n;i++)

            y[p++]=i;

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

            if(sa[i]>=j)

                y[p++]=sa[i]-j;

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

            wv[i]=x[y[i]];

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

            ws1[i]=;

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

            ws1[wv[i]]++;

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

            ws1[i]+=ws1[i-];

        for(i=n-;i>=;i--)

            sa[--ws1[wv[i]]]=y[i];

        for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)

            x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

    }

}

void calheight(int *r,int *sa,int n)

{

    int i,j,k=;

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

        rank1[sa[i]]=i;

    for(i=;i<n;height[rank1[i++]]=k)

        for(k?k--:,j=sa[rank1[i]-];r[i+k]==r[j+k];k++) ;

}

void RMQ(int n)//RMQ预处理

{

    int i,j;

    memset(dp,,sizeof(dp));

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

        dp[i][]=height[i];

    for(j=;(<<j)<=n;j++)

        for(i=;i+(<<j)-<=n;i++)

            dp[i][j]=mmin(dp[i][j-],dp[i+(<<(j-))][j-]);

}

int lcp(int l,int r)//求最长公共前缀

{

    int a=rank1[l],b=rank1[r];

    if(a>b)

        swap(a,b);

    a++;

    int t=(int)(log(double(b-a+))/log(2.00));

    return mmin(dp[a][t],dp[b-(<<t)+][t]);

}

int main()

{

    int T,i,k,ca=,s,t,ans;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",str);

        k=strlen(str);

        str[k]='';

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

            str[i+k+]=str[k-i-];

        str[*k+]='';

        n=*k+;

        str[n]='\0';

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

            a[i]=(int)str[i];

        da(a,sa,n,'z'+);

        calheight(a,sa,n-);

        RMQ(n-);

        ans=;

        memset(vis,,sizeof(vis));

        s=;

        for(i=;i<n;i++)//奇数的时候

        {

            s=mmin(s,height[i]);

            if(vis[*k-sa[i]])

            {

                t=lcp(sa[i],*k-sa[i]);

                if(t>s)

                {

                    ans+=t-s;

                    s=t;

                }

            }

            else

                vis[sa[i]]=;

        }

        memset(vis,,sizeof(vis));

        s=;

        for(i=;i<n;i++)//偶数的时候

        {

            s=mmin(s,height[i]);

            if(!sa[i])

                continue;

            if(vis[*k-sa[i]+])

            {

                t=lcp(sa[i],*k-sa[i]+);

                if(t>s)

                {

                    ans+=t-s;

                    s=t;

                }

            }

            else

                vis[sa[i]]=;

        }

        printf("Case #%d: %d\n",++ca,ans);

    }

    return ;

}