#include<bits/stdc++.h>
#define ci const int
using namespace std;
ci N=1e6+5;
int n,a[N],l[130][N],r[130][N];
char s[N];
inline void Max(int &x,ci v){
	x=x>v?x:v;
}
inline void Min(int &x,ci v){
	x=x<v?x:v;
}
void Init(){
	for(int i=0;i<130;++i)
		for(int j=1;j<=n;++j)
			l[i][j]=r[i][j]=0;
}
void Work(){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;++i)a[i]=s[i]^48;
	++n;
	for(int i=1;i<=n;++i)l[0][i]=r[0][i]=i;
	for(int T=1;;++T){
		for(int i=1;i<=n;++i)l[T][i]=l[T-1][i],r[T][i]=r[T-1][i];
		for(int i=1;i<n;++i)
			if(a[i]<=T)
				Max(r[T][l[T-a[i]][i]],r[T-a[i]][i+1]),
				Min(l[T][r[T-a[i]][i+1]],l[T-a[i]][i]);
		for(int i=2;i<=n;++i)Max(r[T][i],r[T][i-1]);
		for(int i=n-1;i;--i)Min(l[T][i],l[T][i+1]);
		if(r[T][1]==n){
			printf("%d\n",T);
			return;
		}
	}
}
int main(){
	int T;scanf("%d",&T);
	for(int i=1;i<=T;++i)printf("Case #%d: ",i),Work(),Init();
	return 0;
}