#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e6+5;
int T,n,a[N],L[10][N],R[10][N];
string C;
inline void sol()
{
	for(int i=0;i<(n=C.size());i++) a[i+1]=C[i]-'0';
	for(int s=0;;s++)
	{
		int rs=s%10;
		for(int i=0;i<=n+1;i++) L[rs][i]=i+1,R[rs][i]=i-1;
		for(int i=1;i<=n;i++) if(s>=a[i])
		{
			int t=(s-a[i]+10)%10,l=L[t][i-1],r=R[t][i+1];
			L[rs][r]=min(L[rs][r],l);
			R[rs][l]=max(R[rs][l],r);
		}
		for(int i=2;i<=n;i++) R[rs][i]=max(R[rs][i],R[rs][i-1]);
		for(int i=n-1;i;i--) L[rs][i]=min(L[rs][i],L[rs][i+1]);
		if(R[rs][1]>=n) return cout<<s<<"\n",void();
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
	for(int i=1;i<=T;i++) cin>>C,cout<<"Case #"<<i<<": ",sol();
	return 0;
}