#include<bits/stdc++.h>
using namespace std;
const int N = 1000000+10;
string s,tmp;
int d[N*2];
int main(){
    int T,cn = 0;
    cin>>T;
    while(T--){
    	cin>>tmp;
    	cn++;
    	cout<<"Case #"<<cn<<": ";
    	int n = tmp.size();
    	long long cnt = 0;
    	s.resize(n*2+1);
    	for(int i = 0;i < n;i++)s[n*2+1] = tmp[i];
    	n = n*2+1;
    	int l = -1,r = -1;
    	for(int i = 0;i < n;i++){
    	    if(i > r)d[i] = 1;
			else d[i] = min(d[l+r-i],r-i+1);
			while(i-d[i]>= 0&&i+d[i] < n&&s[i-d[i]] == s[i+d[i]])d[i]++;
			if(i+d[i]-1 > r){
				r = i+d[i]-1;
				l = i-d[i]+1;
			}
			cnt += d[i]/2;
		}
		cout<<cnt<<endl;
	}
}