#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

const int INF = 1e9+;

const int MAXN = ;

int dp[MAXN][MAXN];

char str[MAXN];

int DFS(int L,int R)

{

    if(dp[L][R] != -) return dp[L][R];

    if(L >= R) return dp[L][R] = ;

    dp[L][R] = INF;

    for(int i=L; i<=R; i++)

    {

        if(str[L] == str[i])

            dp[L][R] = min(dp[L][R], R - i + DFS(L+,i-));

        dp[L][R] = min(dp[L][R], DFS(L+,i)+R-i+);

    }

    return dp[L][R];

}

int main()

{

    int T, cas = , n;

    scanf("%d", &T);

    while(T --)

    {

        memset(dp, -, sizeof(dp));

        scanf("%s", str);

        printf("Case %d: %d\n",cas++, DFS(, strlen(str)-));

    }

    return ;

}