/*hdu6212[区间dp] 2017青岛ACM-ICPC网络赛*/

#include <bits/stdc++.h>

using namespace std;

int T, n, tot = , kase = ;

char s[];

int dp[][], cnt[], col[];

void solve() {

    memset(dp, 0x3f, sizeof(dp));

    tot = ;

    n = strlen(s);

    cnt[tot] = , col[tot] = s[] - '';

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

        if (s[i] == s[i - ]) cnt[tot]++;

        else {

            cnt[++tot] = ;

            col[tot] = s[i] - '';

        }

    }

    n = tot;

    for (int i = ; i <= n; i++) dp[i][] = cnt[i] >=  ?  : ;

    for (int j = ; j <= n; j++) {

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

            if (col[i] == col[i + j - ]) {

                if (cnt[i] + cnt[i + j - ] < ) {

                    dp[i][j] = dp[i + ][j - ] + (cnt[i] + cnt[i + j - ] == );

                    for (int k = ; k < j; k++) {

                        if (col[i + k - ] == col[i] && cnt[i + k - ] == ) {

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

                        }

                    }

                }

                else dp[i][j] = dp[i + ][j - ];

            }

            for (int k = ; k < j; k++) {

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

            }

        }

    }

    printf("Case #%d: %d\n", kase++, dp[][n]);

}

int main() {

    scanf("%d", &T);

    while (T--) {

        scanf("%s", s);

        solve();

    }

    return ;

}

// 011011100000001010101110011000 ans=4

// 10110011001101  ans=3