#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,c[MAXN],L[10][MAXN],R[10][MAXN];
char str[MAXN];
int solve() {
	scanf("%s",str+1),n=strlen(str+1);
	for(int i=1;i<=n;++i) c[i]=str[i]-'0';
	for(int x=0;;++x) {
		int *l=L[x%10],*r=R[x%10];
		for(int i=0;i<=n+1;++i) r[i]=i-1,l[i]=i+1;
		for(int i=1;i<=n;++i) if(c[i]<=x) {
			int y=(x+10-c[i])%10;
			int zl=L[y][i-1],zr=R[y][i+1];
			r[zl]=max(r[zl],zr),l[zr]=min(l[zr],zl);
		}
		for(int i=2;i<=n;++i) r[i]=max(r[i],r[i-1]);
		for(int i=n-1;i;--i) l[i]=min(l[i],l[i+1]);
		if(r[1]>=n) return x;
	}
}
signed main() {
	int T; scanf("%d",&T);
	for(int i=1;i<=T;++i) printf("Case #%d: %d\n",i,solve());
	return 0;
}