#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[N][10],R[N][10];
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[i][now]=i+1,R[i][now]=i-1;
		for(int k=1;k<=n;k++){
			if(c>=a[k]){
				int x=L[k-1][(c-a[k])%10],y=R[k+1][(c-a[k])%10];
				L[y][now]=min(L[y][now],x);
				R[x][now]=max(R[x][now],y);
			}
		}
		for(int i=n-1;i>=1;i--)L[i][now]=min(L[i][now],L[i+1][now]);
		for(int i=2;i<=n;i++) R[i][now]=max(R[i][now],R[i-1][now]);
		if(R[1][now]>=n||L[n][now]<=1) return c;
	}
	return 0;
}

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