#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 1000010, X = 190;
char c[N];
int n, a[N], f[X][N], g[X][N];
void cmx(int &x, int y) {if(x < y) x = y;}
void cmn(int &x, int y) {if(x > y) x = y;}

int main(){
	int T; scanf("%d", &T); rep(_, 1, T){
		scanf("%s", c+1); n = strlen(c+1);
		rep(i, 1, n) a[i] = c[i] ^ 48;
		memset(f, 0, sizeof(f));
		memset(g, 0x3f, sizeof(g));
		rep(i, 1, n) f[0][i] = i-1, g[0][i] = i+1;
		rep(i, 0, X-1) g[i][0] = 1, f[i][n+1] = n;
		rep(k, 0, X-1){
			if(k) rep(i, 1, n)
				cmx(f[k][i], f[k-1][i]), cmn(g[k][i], g[k-1][i]);
			rep(i, 2, n) cmx(f[k][i], f[k][i-1]);
			per(i, n-1, 1) cmn(g[k][i], g[k][i+1]);
			// printf("%d %d\n", k, f[k][1]);
			if(f[k][1] == n) {printf("Case #%d: %d\n", _, k); break;}
			rep(i, 1, n)
				cmx(f[k+a[i]][g[k][i-1]], f[k][i+1]), 
				cmn(g[k+a[i]][f[k][i+1]], g[k][i-1]);
		}
	}
	return 0;
}