#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef long long int ll;
typedef vector< pair<int, int> > vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long int> vll;
typedef pair<int, int> pii;

const ll INF = 1e18;
const int inf = 1e9;
const int MOD = 1e9 + 7;
const int nax = 1000000 + 10;

int n, arr[nax];
string s;

bool is1(int a, int b, string s1)
{
    int start = 0;
    for(int i = a; i <= b; i++)
        if(s[i] != s1[start++]) return false;
    return true;
}
bool is(int cur, string s1)
{
    int len = s1.length();
    int i = 0, j = len - 1;
    while(j <= cur)
    {
        if(is1(i, j, s1))
            return true;
        i++, j++;
    }
    return false;
}
map< pair<int, string>, int> dp;

int solve(int cur, string cip)
{
    //cout << cur << " " << cip << endl;
    if(cur >= n - 1) return 0;
    if(dp.count(mp(cur, cip)))
        return dp[mp(cur, cip)];
    int ans = 1 + solve(cur + 1, cip);
    string abhi = "";
    for(int j = cur + 1; j < n; j++)
    {
        abhi += s[j];
        if(is(cur, abhi) && cip != abhi)
            ans = min(ans, 2 + solve(cur + (int)abhi.length(), abhi));
    }
    if(cip.length() > 0)
    {
        int len = cip.length();
        if(is1(cur + 1, cur + len, cip))
            ans = min(ans, 1 + solve(cur + len, cip));
    }
    return dp[mp(cur, cip)] = ans;
}
int main()
{
    ios::sync_with_stdio(0);
    freopen("inp.in", "r", stdin);
    freopen("out.txt", "w", stdout);
    int t, tt = 0;
    cin >> t;
    while(t--)
    {
        dp.clear();
        tt++;
        cin >> s;
        n = s.length();
        string emp = "";
        cout << "Case #" << tt << ": " << solve(-1, emp) << endl;
    }
    return 0;
}