/*

     题意：三种操作，插入，删除，替换，问最少操作数使得字符串变成回文串

     区间DP：有一道类似的题，有点不同的是可以替换，那么两端点不同的时候可以替换掉一个后成回文，

             即dp[j+1][k-1] + 1，还有这道题没有要求打印

 */

 /************************************************

 * Author        :Running_Time

 * Created Time  :2015-8-17 15:45:22

 * File Name     :UVA_10739.cpp

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef long long ll;

 const int MAXN = 1e3 + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 int dp[MAXN][MAXN];

 char str[MAXN];

 int work(void) {

     memset (dp, , sizeof (dp));

     int len = strlen (str);

     for (int i=; i<=len; ++i)  {

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

             int k = j + i - ;

             int &res = dp[j][k] = INF;

             if (str[j] == str[k])   res = dp[j+][k-];

             res = min (res, min (dp[j+][k], min (dp[j][k-], dp[j+][k-])) + );

         }

     }

     return dp[][len-];

 }

 int main(void)    {     //UVA 10739 String to Palindrome

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

     while (T--) {

         scanf ("%s", str);

         printf ("Case %d: %d\n", ++cas, work ());

     }

     return ;

 }