#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<cmath>

#include<set>

#include<vector>

#include<list>

using namespace std;



typedef long long ll;

typedef pair<double,double>ppd;

const double PI = acos(-1.);

const double eps = (1e-9);

const int MOD=10007;

const int N=1005;

char s[N];

int ans[N][N];

int dp(int l,int r)

{

    if(ans[l][r]!=-1)

    return ans[l][r];//記憶化

    ans[l][r]=0;

    if(l==r)//邊界

    return (ans[l][r]=1);

    if(l+1==r)//邊界

    {

        ans[l][r]=2;

        if(s[l]==s[r])

        ++ans[l][r];

        return ans[l][r];

    }

    if(s[l]==s[r])//以l和r 為左右端點(diǎn)的情況 其中的1表示的是單獨(dú)的l和r也是一個(gè)回文

    ans[l][r]+=dp(l+1,r-1)+1;

    ans[l][r]+=(dp(l+1,r)+dp(l,r-1)-dp(l+1,r-1));//把多加的減掉

    ans[l][r]%=MOD;

    if(ans[l][r]<0)

    ans[l][r]+=MOD;

    return ans[l][r];

}

int main()

{

    //freopen("data.in","r",stdin);

    int T;

    scanf("%d",&T);

    for(int c=1;c<=T;++c)

    {

        scanf("%s",s);

        memset(ans,-1,sizeof(ans));

        printf("Case %d: %d\n",c,dp(0,strlen(s)-1));

    }

    return 0;

}