#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=1e3+5;
const int INF=0x3f3f3f3f;
const int MOD=10007;

int dp[maxn][maxn];
char str[maxn];

int main(){
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        memset(dp,0,sizeof(dp));
        scanf("%s",str+1);
        int n=strlen(str+1);
        for(int i=1;i<=n;i++) dp[i][i]=1;   //单个字母肯定是回文串
        for(int d=1;d<n;d++)
        for(int i=1;i+d<=n;i++){
            int j=i+d;
            dp[i][j]=(dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]+MOD)%MOD;
            if(str[i]==str[j]) dp[i][j]=(dp[i][j]+dp[i+1][j-1]+1+MOD)%MOD;
        }
        printf("Case %d: %d\n",t,dp[1][n]);
    }
    return 0;
}