#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n,a[N];
char s[N];
namespace sub1{
	inline bool check(){
		for(int i = 1;i<=n;++i)if(a[i] ^ 1)return false;
		return true;
	}
	void solve(){
		int ans = 0;
		while((1 << ans) < n)++ans;
		printf("%d",ans);
	}
}
namespace sub2{
	#define N 110
	int f[N][N];
	int kp[N][N];
	int dfs(int l,int r){
		if(l == r)return f[l][r] = 0;
		if(l + 1 == r)return kp[l][r] = r,f[l][r] = a[r];
		if(f[l][r] != inf)return f[l][r];
		int &res = f[l][r];
		
		for(int i = l+1;i<=r;++i){
			if(res >= max(dfs(l,i-1),dfs(i,r))+a[i]){
				res = max(dfs(l,i-1),dfs(i,r))+a[i];
				kp[l][r] = i;
			}
		}
		return res;
	}
	void solve(){
		memset(f,0x3f,sizeof f);
		printf("%d",dfs(0,n));
	}
	#undef N
}
namespace sub3{
	int L[10][N],R[10][N];
	void solve(){
		for(int val = 0;val<=180;++val){
			int now = val % 10;
			for(int i = 0;i<=n;++i)L[now][i] = R[now][i] = i;
			for(int i = 1;i<=n;++i)if(a[i] <= val){
				int tl = L[(val - a[i]) % 10][i-1], tr = R[(val - a[i]) % 10][i];
				L[now][tr] = min(L[now][tr],tl);
				R[now][tl] = max(R[now][tl],tr);
			}
			for(int i = n-1;~i;--i)L[now][i] = min(L[now][i+1],L[now][i]);
			for(int i = 1;i<=n;++i)R[now][i] = max(R[now][i-1],R[now][i]);
			if(L[now][n] <= 1 || R[now][1] >= n)return printf("%d",val),void();
		}
		assert(0);
	}
}

void work(){
	scanf("%s",s+1), n = strlen(s+1);
	for(int i = 1;i<=n;++i)a[i] = s[i] - 48;
	if(sub1::check())sub1::solve();
	else if(n <= 100)sub2::solve();
	else sub3::solve();
	puts("");
}

int main(){
	int T; scanf("%d",&T);
	for(int cas = 1;cas <= T;++cas){
		printf("Case #%d: ",cas);
		work();
	}
	return 0;
}