#include<bits/stdc++.h>
#define ull unsigned long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
using namespace std;
int rd(){
    int x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353;
int n,a[N],L[10][N],R[10][N];
char s[N];
int solve(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) a[i]=(s[i]-'0');
	for(int c=0;c<=180;c++){
		int now=c%10;
		for(int i=0;i<=n+1;i++) L[now][i]=i+1,R[now][i]=i-1;
		for(int k=1;k<=n;k++){
			if(c>=a[k]){
				int x=L[(c-a[k])%10][k-1],y=R[(c-a[k])%10][k+1];
				L[now][y]=min(L[now][y],x);
				R[now][x]=max(R[now][x],y);
			}
		}
		for(int i=n-1;i>=1;i--)L[now][i]=min(L[now][i],L[now][i+1]);
		for(int i=2;i<=n;i++) R[now][i]=max(R[now][i],R[now][i-1]);
		if(R[now][1]>=n||L[now][n]<=1) return c;
	}
	return 0;
}

int main(){
	int T=rd(),t=0;
	while(T--){
		printf("Case #%d: %d\n",++t,solve());
	}
    return 0;
}