#include<bits/stdc++.h>
using namespace std;
int n,m,t,a[1000001],ans,l[10][1000011],r[10][1000011];
string s;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	int sb=t;
	while(t--){
		cin>>s;
		int n=s.size();
		s=" "+s;
		for(int i=1;i<=n;i++){
			a[i]=s[i]-'0';
		}
		ans=0;
		while(1){
			int j=ans%10;
			for(int i=0;i<=n+1;i++){
				l[j][i]=i+1,r[j][i]=i-1;
			}
			for(int i=1;i<=n;i++){
				if(ans-a[i]<0) continue;
				int L=l[(ans-a[i])%10][i-1],R=r[(ans-a[i])%10][i+1];
				l[j][R]=min(l[j][R],L);
				r[j][L]=max(r[j][L],R);
			}
			for(int i=n-1;i>=1;i--){
				l[j][i]=min(l[j][i+1],l[j][i]);
			}
			for(int i=2;i<=n;i++){
				r[j][i]=max(r[j][i-1],r[j][i]);
			}
			if(r[j][1]>=n&&l[j][n]<=1) break;
			ans++;
		}
		cout<<"Case #"<<sb-t<<": "<<ans<<"\n";
	}
	return 0;
}