#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;
	while(tl[1][0]<n){
		step++;
		for(int i=1;i<=n;i++)for(int j=9;j;j--)tl[i][j]=tl[i][j-1],tr[i][j]=tr[i][j-1];
		for(int i=1;i<=n;i++){
			int e=c[i]-'0';
			if(e>step)continue;
			int L=((i==1)?i:tr[i-1][e]),R=((i==n)?i:(tl[i+1][e]));
			L=min(L,i),R=max(R,i);
			if(L<=R)tl[L][0]=max(tl[L][0],R),tr[R][0]=min(tr[R][0],L);
		}
		for(int i=2;i<=n;i++)tl[i][0]=max(tl[i][0],tl[i-1][0]);
		for(int i=n-1;i;i--)tr[i][0]=min(tr[i][0],tr[i+1][0]);
	}
	printf("Case #%d: %d\n",st,step);
} 
int main(){
	int T;cin>>T;for(int i=1;i<=T;i++)sol(i);
	return 0;
}