#define _CRT_SECURE_NO_DEPRECATE#include<stdio.h>  #include<string.h>  #include<cstring>#include<algorithm>  #include<queue>  #include<math.h>  #include<time.h>#include<vector>#include<iostream>#include<map>using namespace std;typedef long long int LL;const int MAXN = 100000*3  + 10;int wa[MAXN],wb[MAXN],wv[MAXN],Ws[MAXN];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){ //??????sa????????(len+1)???????     int i,j,p,*x=wa,*y=wb,*t;     for(i=0;i<m;i++) Ws[i]=0;     for(i=0;i<n;i++) Ws[x[i]=r[i]]++;     for(i=1;i<m;i++) Ws[i]+=Ws[i-1];     for(i=n-1;i>=0;i--) sa[--Ws[x[i]]]=i;     for(j=1,p=1;p<n;j*=2,m=p)     {       for(p=0,i=n-j;i<n;i++) y[p++]=i;       for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;       for(i=0;i<n;i++) wv[i]=x[y[i]];       for(i=0;i<m;i++) Ws[i]=0;       for(i=0;i<n;i++) Ws[wv[i]]++;       for(i=1;i<m;i++) Ws[i]+=Ws[i-1];       for(i=n-1;i>=0;i--) sa[--Ws[wv[i]]]=y[i];       for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)       x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;     }     return;}int Rank[MAXN],height[MAXN]; //height[0]:sa[1]?sa[0]?lcpvoid calheight(int *r,int *sa,int n){ //??????sa???????(len)     int i,j,k=0;     for(i=1;i<=n;i++) Rank[sa[i]]=i;     for(i=0;i<n;height[Rank[i++]]=k)     for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);     return;}int RMQ[MAXN],mm[MAXN],best[20][MAXN];void initRMQ(int n){     int i,j,a,b;     for(mm[0]=-1,i=1;i<=n;i++)     mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];     for(i=1;i<=n;i++) best[0][i]=i;     for(i=1;i<=mm[n];i++)     for(j=1;j<=n+1-(1<<i);j++){       a=best[i-1][j];       b=best[i-1][j+(1<<(i-1))];       if(RMQ[a]<RMQ[b]) best[i][j]=a;       else best[i][j]=b;     }     return;}int askRMQ(int a,int b){    int t;    t=mm[b-a+1];b-=(1<<t)-1;    a=best[t][a];b=best[t][b];    return RMQ[a]<RMQ[b]?a:b;}int lcp(int a,int b){    int t;    a=Rank[a];b=Rank[b];    if(a>b) {t=a;a=b;b=t;}    return(height[askRMQ(a+1,b)]);}char str[MAXN],dstr[MAXN];int lenstr,lendstr,p[MAXN],r[MAXN],sa[MAXN];void init(char *s){    dstr[0]=‘$‘; dstr[1]=‘#‘;    for(int i=0;i<lenstr;i++){        dstr[i*2+2]=str[i]; dstr[i*2+3]=‘#‘;    }    lendstr=lenstr*2+2; dstr[lendstr]=‘*‘;}void manacher(){    memset(p,0,sizeof(p)); int id=0,mx=0;    for(int i=1;i<lendstr;i++){        if(mx>i){ p[i]=min(p[2*id-i],mx-i); }        else{ p[i]=1; }        while(dstr[i-p[i]]==dstr[i+p[i]]){ p[i]++; }        if(p[i]+i>mx){  mx=p[i]+i; id=i; }    }}void solve(){    int ans=0,tmp=0;    for(int i=1;i<=lendstr;i++){        tmp=min(tmp,height[i]);        if(p[sa[i]]<=tmp){            continue;            }        ans+=(p[sa[i]]-tmp)/2;        tmp=p[sa[i]];    }    printf("%d\n",ans);}int main(){//#ifdef kirito//    freopen("in.txt", "r", stdin);//    freopen("out.txt", "w", stdout);//#endif//    int start = clock();    int t,Case=1;    scanf("%d",&t);    while (t--){        scanf("%s",str); lenstr=strlen(str); init(str); manacher();        for(int i=0;i<=lendstr;i++){            if(i==lendstr){r[i]=0; continue;}            r[i]=(int)dstr[i];        }        da(r, sa, lendstr+1,256);        calheight(r, sa, lendstr);//        printf("len=%d\n",lendstr);        printf("Case #%d: ",Case++); solve();    }//#ifdef LOCAL_TIME//    cout << "[Finished in " << clock() - start << " ms]" << endl;//#endif    return 0;}