#include<bits/stdc++.h>
using namespace std;
inline int rd(){
	int s=0,w=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';
	return s*w;
}
const int N=1e6+5;
char a[N];int T,n,c[N];
int L[10][N],R[10][N];
inline int solve(){
	scanf("%s",a+1);
	n=strlen(a+1);
	for(int i=1;i<=n;++i)c[i]=a[i]-'0';
	for(int v=0;v<=181;++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(v<c[i])continue;
			int x=L[(v-c[i])%10][i-1],y=R[(v-c[i])%10][i+1];
			L[v][y]=x;R[v][x]=y;
		}
		for(int i=2;i<=n;++i)R[v][i]=max(R[v][i-1],R[v][i]);
		for(int i=n-1;i;--i)L[v][i]=min(L[v][i+1],L[v][i]);
		if(L[v][n]==1||R[v][1]==n)return v;
	}
}
int main(){
	T=rd();
	for(int i=1;i<=T;++i)printf("Case #%d: %d\n",i,solve());
	return 0;
}