#include<bits/stdc++.h>
using namespace std;
int t,n,l[10][1000010],r[10][1000010];
char s[1000001];
int main(){
	scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%s",s+1),n=strlen(s+1);
        for(int v=0;;v++){
            int u=v%10;
            for(int j=0;j<=n+1;j++) l[u][j]=j+1,r[u][j]=j-1;
            for(int j=1;j<=n;j++){
                if(s[j]-48>v) continue;
                int a=l[(u-s[j]+58)%10][j-1],b=r[(u-s[j]+58)%10][j+1];
                r[u][a]=max(r[u][a],b);
                l[u][b]=min(l[u][b],a);
            }
            for(int j=1;j<=n;j++) r[u][j]=max(r[u][j],r[u][j-1]);
            for(int j=n;j>=1;j--) l[u][j]=min(l[u][j],l[u][j+1]);
            if(l[u][n]==1) printf("Case #%d: %d\n",i,v);
            if(l[u][n]==1) break;
        }
    }
    return 0;
}