#pragma GCC optimize("Ofast", "inline", "fast-math")

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

const int N = 1000010, M = 181;

char cost[N];
int n;
int f[N][M], g[N][M];

signed main() {
    #ifndef XuYueming
    // freopen("cost.in", "r", stdin);
    // freopen("cost.out", "w", stdout);
    #endif
    int t; scanf("%d", &t);
    for (int _ = 1; _ <= t; ++_) {
        printf("Case #%d: ", _);
        scanf("%s", cost + 1);
        n = strlen(cost + 1);
        for (int i = 1; i <= n + 1; ++i)
            for (int v = 0; v < M; ++v)
                f[i][v] = g[i][v] = i;
        for (int j = 1; j < M; ++j) {
            for (int i = 1; i <= n; ++i) {
                int v = cost[i] ^ 48;
                if (j < v) continue;
                f[g[i][j - v]][j] = max(f[g[i][j - v]][j], f[i + 1][j - v]);
                g[f[i + 1][j - v]][j] = min(g[f[i + 1][j - v]][j], g[i][j - v]);
            }
            for (int i = 2; i <= n + 1; ++i)
                f[i][j] = max(f[i][j], f[i - 1][j]);
            for (int i = n; i >= 1; --i)
                g[i][j] = min(g[i][j], g[i + 1][j]);
            if (f[1][j] > n) {
                printf("%d\n", j);
                break;
            }
        }
    }
    return 0;
}