#include <bits/stdc++.h>
using namespace std;
const int N=1e6+2,M=10;
char A[N];
int a[N],L[M][N],R[M][N];
void solve(int o){
    scanf("%s",A+1);int n=strlen(A+1);
    for(int i=1;i<=n;i++)a[i]=A[i]-'0';
    for(int v=0;;v++){
        int now=v%10;
        for(int i=0;i<=n+1;i++)L[now][i]=i+1,R[now][i]=i-1;
        for(int i=1;i<=n;i++)if(a[i]<=v){
            int l=L[(v-a[i])%10][i-1],r=R[(v-a[i])%10][i+1];
            R[now][l]=max(R[now][l],r);
            L[now][r]=min(L[now][r],l);
        }
        for(int i=2;i<=n;i++)R[now][i]=max(R[now][i],R[now][i-1]);
        for(int i=n-1;i>=1;i--)L[now][i]=min(L[now][i],L[now][i+1]);
        if(R[now][1]>=n){
            printf("Case #%d: %d\n",o,v);
            return;
        }
    }

}
int main() {
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)solve(i);
    return 0;
}