#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

char a[70];

ll  dp[70][70];

int main(){

	int T; scanf("%d",&T);

	int n;

	int ca = 0;

	while(T--){

		memset(dp,0,sizeof(dp));

		scanf("%s",a+1);

		int n = strlen(a+1);

		for(int i = 1; i <= n; ++i){

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

				int l = j; int r = l+i-1;

				dp[l][r] += dp[l+1][r];

				dp[l][r] += dp[l][r-1];

				if(a[l] == a[r]) dp[l][r] ++;

				else dp[l][r] -= dp[l+1][r-1];

			}

		}

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

	}

	return 0;

}