#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline void work(int k){
	if(k<0){
		putchar('-');
		k=-k;
	}
	if(k>9)
		work(k/10);
	putchar(k%10+'0');
}
/*
首先有暴力dp
定义dp[l][r]表示在[l,r]的最坏情况最小代价
dp[l][r]=min(c[k]+max(dp[l][k-1],dp[k+1][r]))
因为c[i]<=9,所以dp中的值最多就是clogn的,并且观察式子对于同一个l,当l<=r<=r'的时候dp[l][r]<=dp[l][r'],因为不同区间是取max
对于这种值域很小并且dp值有单调性就可以通过维护每个值域的端点值来维护状态
定义L[c][i]表示右端点为i是,最小的l使得dp[l][i]<=c,R[c][i]同理,维护最大的r
每次转移枚举端点,x=L[c-a[k]][k-1],y=R[c-a[k]][k+1]
L[c][y]=min(x),R[c][x]=max(y)
因为dp值的单调性,再做一个前/后缀,min/max就行了,dp[l][r]<=dp[l][r']->L[v][r]<=L[v][r'],L同理
滚动数组
*/
int t,val[1000005],L[10][1000005],R[10][1000005];
char s[1000005];
int solve(){
	int n=strlen(s+1);
	for(int i=1;i<=n;i++){
		val[i]=s[i]-'0';
	}
	for(int v=0;;v++){
		for(int i=0;i<=n+1;i++){
			L[v%10][i]=i+1;
			R[v%10][i]=i-1;
		}
		for(int i=1;i<=n;i++){
			if(val[i]<=v){
				int l=L[(v-val[i])%10][i-1],r=R[(v-val[i])%10][i+1];
				L[v%10][r]=min(L[v%10][r],l);
				R[v%10][l]=max(R[v%10][l],r);
			}
		}
		for(int i=2;i<=n;i++){
			R[v%10][i]=max(R[v%10][i],R[v%10][i-1]);/*dp[l][r]<=dp[l'][r],l'<=l<=r*/
		}
		for(int i=n-1;i;i--){
			L[v%10][i]=min(L[v%10][i],L[v%10][i+1]);/*dp[l][r]<=dp[l][r'],l<=r<=r'*/
		}
		if(R[v%10][1]>=n)
			return v;
	}
}
int main(){
	t=read();
	for(int i=1;i<=t;i++){
		scanf("%s",s+1);
		printf("Case #%d: %d\n",i,solve());
	}
	return 0;
}