#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define PII  pair<int,int> 
#define fi first
#define se second
#define MP make_pair
inline int read()
{
	int s=0;char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())s=(s<<1)+(s<<3)+(c^48);
	return s;
}
const int N=1e6+7;
char s[N];
int L[10][N],R[10][N];
int main()
{
	int tt=read(),n;
	for(int num=1;num<=tt;num++)
	{
		scanf("%s",s+1);
		n=strlen(s+1);
		for(int i=0;i<=9;i++)
			for(int j=0;j<=n+1;j++)
				L[i][j]=j+1,R[i][j]=j-1;
		for(int i=1;i<=n;i++)L[s[i]^48][i]=i,R[s[i]^48][i]=i;
		for(int i=0;i<=180;i++)
		{
			int x=i%10;
			if(R[x][1]==n)
			{
				printf("Case #%d: %d\n",num,i);
				break;
			}
			int y=(x+9)%10,l=0,r=0;
			if(i)for(int j=1;j<=n;j++)L[x][j]=min(L[x][j],L[y][j]),R[x][j]=max(R[x][j],R[y][j]);
			for(int i=1;i<=n;i++)R[x][i]=max(R[x][i],R[x][i-1]);
			for(int i=n-1;i;i--)L[x][i]=min(L[x][i],L[x][i+1]);
			for(int i=1;i<=n;i++)
			{
				y=(x+s[i]-'0')%10;
				l=L[x][i-1],r=R[x][i+1];
				R[y][l]=max(R[y][l],r);
				L[y][r]=min(L[y][r],l);
			}
		}
	}
}