#include<bits/stdc++.h>

using namespace std;
int T;
char s[1000005];
int L[10][1000005],R[10][1000005];
int now,n;
int main(){
    scanf("%d",&T);
    int tid=0;
    while(T--){
        scanf("%s",s+1);n=strlen(s+1);
        for(int i=0;i<=9;i++)
            for(int j=0;j<=n+1;j++)
                L[i][j]=j+1,R[i][j]=j-1;
        for(int i=1;i<=n;i++)L[s[i]-'0'][i]=R[s[i]-'0'][i]=i;
        for(int i=0;i<=180;i++){
            int x=i%10;
            if(R[x][1]==n){
                printf("Case #%d: %d\n",++tid,i);
                break;
            }
            int y=(x+9)%10,l=0,r=0;
            if(i)for(int j=1;j<=n;j++)L[x][j]=min(L[y][j],L[x][j]),R[x][j]=max(R[x][j],R[y][j]);
            for(int i=1;i<=n;i++)L[x][i]=max(L[x][i],L[x][i-1]);
            for(int i=n-1;i>=1;i--)R[x][i]=min(R[x][i],R[x][i+1]);
            for(int i=1;i<=n;i++){
                y=(x+s[i]-'0')%10;
                l=L[x][i-1];r=R[x][i+1];
                R[y][l]=max(R[y][l],r);
                L[y][r]=min(L[y][r],l);
            }
        }
    }
    return 0;
}