#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

// #define Hydro

const int N = 2010;

char cost[N];
int n;
int f[N][N];

int dfs(int l, int r) {
    if (l > r) return 0;
    if (f[l][r]) return f[l][r];
    int& res = f[l][r] = 0x3f3f3f3f;
    for (int i = l; i <= r; ++i)
        res = min(res, max(dfs(l, i - 1), dfs(i + 1, r)) + (cost[i] ^ 48));
    return res;
}

void solve() {
    scanf("%s", cost + 1);
    n = strlen(cost + 1);
    for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        f[i][j] = 0;
    printf("%d", dfs(1, n));
}

signed main() {
    #ifdef Hydro
    freopen("cost.in", "r", stdin);
    freopen("cost.out", "w", stdout);
    solve();
    #endif
    int t; scanf("%d", &t);
    for (int i = 1; i <= t; ++i)
        printf("Case #%d: ", i), solve();
    return 0;
}