#include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<stack>

 using namespace std;

 #define inf 0x3f3f3f3f

 int f[][];

 char s[];

 int main()

 {

     int N=,M,i,j,k,t;

     cin>>t;

     for(int xx=;xx<=t;++xx)

     {

         cin>>(s+);

         int n=strlen(s+);

         memset(f,,sizeof(f));

         for(int len=;len<=n;++len)

         {

             for(i=,j=len;j<=n;++i,++j)

             {

                 f[i][j]=inf;

                 if(s[i]==s[j]) f[i][j]=f[i+][j-];

                 f[i][j]=min(f[i][j],min(min(f[i][j-]+,f[i+][j]+),f[i+][j-]+));

             }

         }

         printf("Case %d: %d\n",xx,f[][n]);

     }

     return ;

 }