#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=1e6+5,V=10;
char s[N];
int n,L[V][N],R[V][N];
inline void solve(int cs){
    scanf("%s",s+1),n=strlen(s+1);
    memset(L,0,sizeof L),memset(R,0,sizeof R);
    for(int i=0;i<=n+1;i++) L[0][i]=i+1,R[0][i]=i-1;
    for(int ans=1;;ans++){
        for(int i=0;i<=n+1;i++) L[ans%10][i]=i+1,R[ans%10][i]=i-1;
        for(int i=1;i<=n;i++) if(ans>=int(s[i]-'0')){
            int l=L[(ans-int(s[i]-'0'))%10][i-1],r=R[(ans-int(s[i]-'0'))%10][i+1];
            L[ans%10][r]=std::min(L[ans%10][r],l);
            R[ans%10][l]=std::max(R[ans%10][l],r);
        }
        for(int i=n;i>=1;i--) L[ans%10][i]=std::min(L[ans%10][i],L[ans%10][i+1]);
        for(int i=1;i<=n;i++) R[ans%10][i]=std::max(R[ans%10][i],R[ans%10][i-1]);
        if(L[ans%10][n]<=1||R[ans%10][1]>=n) return printf("Case #%d: %d\n",cs,ans),void();
    }
}
int main(){
    int cs; scanf("%d",&cs);
    for(int i=1;i<=cs;i++) solve(i);
    return 0;
}