#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,V=180;
int n,c[N],id[V+10];
int L[12][N],R[12][N];
int s1[N],s2[N];
bool cmp(pair<int,int>x,pair<int,int>y){return x.second>y.second;}
void sol(int T){
	static char ch[N];scanf("%s",ch+1);
	n=strlen(ch+1);if(n>10000)return;
	for(int i=0;i<=10;i++)for(int j=0;j<=n+1;j++)L[i][j]=R[i][j]=0;
	for(int i=1;i<=n;i++)c[i]=ch[i]-'0';
	for(int i=0;i<=n+1;i++)L[0][i]=i+1,R[0][i]=i-1;
	for(int i=0;i<9;i++)id[i]=i;
	for(int i=10;i<=V;i++)id[i]=id[i-10];
	cout<<"Case #"<<T<<": ";
	for(int v=1;;v++){
		// vector<pair<int,int> >ve;
		for(int i=0;i<=n+1;i++)s1[i]=0,s2[i]=n+1;
		for(int i=1;i<=n;i++){
			if(v>=c[i]){
				int l=L[id[v-c[i]]][i-1],r=R[id[v-c[i]]][i+1];
				// ve.push_back({l,r});
				s1[l]=max(s1[l],r);
				s2[r]=min(s2[r],l);
				// cout<<i<<" "<<l<<" "<<r<<endl;
			}
		}
		int mx=0;
		// sort(ve.begin(),ve.end());
		for(int i=1,j=0;i<=n;i++){
			mx=max(mx,s1[i]);
			// while(j<ve.size()&&ve[j].first<=i)mx=max(mx,ve[j].second),j++;
			R[id[v]][i]=mx;
		}
		int mi=n;
		// sort(ve.begin(),ve.end(),cmp);
		// for(pair<int,int>i:ve){
		// 	cout<<i.first<<" "<<i.second<<"  ";
		// }cout<<endl;
		for(int i=n,j=0;i>=0;i--){
			mi=min(mi,s2[i]);
			// while(j<ve.size()&&ve[j].second>=i)mi=min(mi,ve[j].first),j++;
			L[id[v]][i]=mi;
		}
		// for(int i=1;i<=n;i++)cout<<L[id[v]][i]<<" ";
		// cout<<"  ";
		// for(int i=1;i<=n;i++)cout<<R[id[v]][i]<<" ";
		// cout<<endl;
		if(R[id[v]][1]==n){
			cout<<v<<endl;
			memset(L,0,sizeof(L));
			memset(R,0,sizeof(R));
			return ;
		}
	}
}
signed main(){
	int t;cin>>t;
	for(int i=1;i<=t;i++)sol(i);
	return 0;
}
/*
g++ 1.cpp -o 1 -std=c++14 -O2 -Wall 
./1
*/