#include<bits/stdc++.h>
using namespace std;
int n,tl[1010000][10],tr[1010000][10];
char c[1000100];
void sol(int st){
	scanf("%s",c+1);n=strlen(c+1);
	for(int i=1;i<=n;i++)for(int j=0;j<10;j++)tl[i][j]=-n-1,tr[i][j]=n+1;
	int step=0,oo=0;
	while(tl[1][oo]<n){
		step++;oo=(oo+9)%10;
		for(int i=1;i<=n;i++){
			int e=c[i]-'0';
			if(e>step)continue;int k=((e-step)%10+10)%10;
			int L=((i==1)?i:tr[i-1][k]),R=((i==n)?i:(tl[i+1][k]));
			L=min(L,i),R=max(R,i);
			if(L<=R)tl[L][oo]=max(tl[L][oo],R),tr[R][oo]=min(tr[R][oo],L);
		}
		for(int i=2;i<=n;i++)tl[i][oo]=max(tl[i][oo],tl[i-1][oo]);
		for(int i=n-1;i;i--)tr[i][oo]=min(tr[i][oo],tr[i+1][oo]);
	}
	printf("Case #%d: %d\n",st,step);
} 
int main(){
	int T;cin>>T;for(int i=1;i<=T;i++)sol(i);
	return 0;
}