#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void read(T &x){x=0;int f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();x*=f;}
template<typename T> inline void write(T x){if(x>9)write(x/10);putchar(x%10+'0');}
const int N=1e6+10;
int T,n,L[15][N],R[15][N],c[N],sl[N],sr[N];
char s[N];
void solve(int T){
    printf("Case #%d: ",T),scanf("%s",s+1),n=strlen(s+1),memset(L,0,sizeof(L)),memset(R,0,sizeof(R));
    for(int i=1;i<=n;++i)c[i]=s[i]-'0';
    for(int i=0;i<=n+1;++i)L[0][i]=i+1,R[0][i]=i-1;
    for(int x=1;;++x){
        for(int i=0;i<=n+1;++i)sl[i]=i-1,sr[i]=i+1;
        for(int i=1;i<=n;++i)if(x>=c[i])
            sl[L[(x-c[i])%10][i-1]]=max(sl[L[(x-c[i])%10][i-1]],R[(x-c[i])%10][i+1]),
            sr[R[(x-c[i])%10][i+1]]=min(sr[R[(x-c[i])%10][i+1]],L[(x-c[i])%10][i-1]);
        int mx=sl[0],mn=sr[n+1];
        for(int i=1;i<=n;++i)mx=max(mx,sl[i]),R[x%10][i]=mx;
        for(int i=n;~i;--i)mn=min(mn,sr[i]),L[x%10][i]=mn;
        if(L[x%10][n]<=1||R[x%10][1]>=n)return write(x),putchar('\n'),void();
    }
}
int main(){
    read(T);
    for(int i=1;i<=T;++i)solve(i);
    return 0;
}