#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n;char s[N];

inline void ckmn(int&x,int y){x>y&&(x=y);}
inline void ckmx(int&x,int y){x<y&&(x=y);}
int L[N][10],R[N][10];
inline void init(int o){for(int i=0;i<=n+1;i++){L[i][o]=i+1;R[i][o]=i-1;}}
inline int solve(){
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=1;i<=n;i++)s[i]-='0';
	memset(L,0,sizeof L);memset(R,0,sizeof R);init(0);
	for(int t=1;;t++){
		int o=t%10;init(o);
		for(int i=1;i<=n;i++)if(s[i]<=t){
			int p=(t-s[i]+10)%10;
			int l=L[i-1][p],r=R[i+1][p];
			ckmn(L[r][o],l);ckmx(R[l][o],r);
		}
		for(int i=n;i>=1;i--)ckmn(L[i][o],L[i+1][o]);
		for(int i=1;i<=n;i++)ckmx(R[i][o],R[i-1][o]);
		if(R[1][o]>=n&&L[n][o]<=1)return t;
	}
}
int main(){
	int T;scanf("%d",&T);
	for(int i=1;i<=T;i++)
		printf("Case #%d: %d\n",i,solve());
	return 0;
}