/**********************************************************************
   *                    Solved By : Md Abdul Alim                     *
   *                    My Team Name: BUBT ILLUSION                   *
   *                    My Blog: onlyprogramming.wordpress.com        *
   *                    My e-mail: alim.cloudofcode@gmail.com         *
   *                    BUBT, CSE, 19th Intake                        *
   *********************************************************************/
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<list>
#include<iomanip>
#include<string>
#include<climits>
#include <sstream>
#include <fstream>
#include<cctype>
#include<time.h>
#include<assert.h>
#include<set>
#include <numeric>
#include <functional>
#include<cstring>
#include<cmath>
#include<iterator>
#include <memory.h>
#include<utility>
#include <ctime>
#include<algorithm>
#define all(v) v.begin(),v.end()
#define read(a) freopen("a.txt","r",stdin)
#define write(b) freopen("b.txt","w",stdout)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define maxall(v) *max_element(all(v))
#define minall(v) *min_element(all(v))
#define pb push_back
#define mk make_pair
#define SORT(v) sort(all(v))
#define UN(v) SORT(v), (v).earse(unique(all(v)),v.end())
#define common(a,b) SORT(a), SORT(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end())
#define uncommon(a,b) SORT(a), SORT(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end())
#define FILL(a,d) memset(a,d,sizeof(a))
#define LL long long
#define PI 2*acos(0.0)
#define pi pair<int,int>
using namespace std;
const int inf=1000000007;
template<class T> T bigmod(T b,T p,T m){if(p==0) return 1;
T res=bigmod(b,p/2,m); res=(res*res)%m; if(p%2==1) res=(res*b)%m; return res;}
template<class T> T gcd(T x, T y){if (y==0) return x; return gcd(y,x%y);}

char s[200];
int dp[105][105];
int f(int i,int j)
{
    if(dp[i][j]!=-1) return dp[i][j];
    if(i==j) return 0;
    else if(j-i==1&&s[i]!=s[j]) return 1;
    else if(j-i==1&&s[i]==s[j]) return 0;
    else if(s[i]==s[j]) return dp[i][j]=f(i+1,j-1);
    return dp[i][j]=1+min(f(i,j-1),f(i+1,j));
}

int main()
{
    int i,j,k,n,d,test,t=0;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%s",s);
        FILL(dp,-1);
        n=strlen(s);
        int flag=0;
        for(i=0,j=n-1;i<n/2;i++,j--)
        {
            if(s[i]!=s[j])
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            printf("Case %d: 0\n",++t);
            continue;
        }
        printf("Case %d: %d\n",++t,f(0,n-1));
    }
    return 0;
}