/*
如果所有c[i]都相等，那就是个二分查找
不相等的话，考虑暴力肯定就是区间dp了
设f[i][j]表示当前把x锁定在区间[i,j]，最坏情况下还需要的最小代价
可以轻松得出转移：f[i][j]=min(c[k]+max(f[i][k-1],f[k+1][j]))
但是这样做O(n^3)，肯定是不行的，时空都爆炸了。

考虑优化
显然，本题的入手点在于c[i]<=9
这意味着dp的值域很小，只有c*logn级别，上界只有180
而且这个dp很显然还有单调性，即若j<=k,f[i][j]<=f[i][k]
那我们就可以考虑用值域来记录dp状态
具体的，设L[j][c]表示区间的右端点在j，左端点最多延伸到L[j][c]，有f[L[j][c]][j]<=c
同理设出R[i][c]
这个东西可以完全代替原来的dp数组，你考虑用它来做原来的转移
显然需要按照c从小到大来转移，所以我们考虑：
假设当前已经求出了所有的L[i][1~c-1]和R[i][1~c-1]，我们如何算出L[i][c]和R[i][c]?
同样尝试去枚举中间的断点k，由于单调性，可以在枚举k的时候只更新离k最近的L和R，最后再推平L和R取前/后缀最优
时间复杂度O(n*c*logn)

空间爆炸了，但注意到我们只需要最多c-9的状态，于是可以滚动数组
*/
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+10;
char s[N];
int n,i,a[N],c,L[N][10],R[N][10];
int work(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(i=1;i<=n;++i)a[i]=(s[i]&15);
	for(c=0;;++c){
		for(i=0;i<=n+1;++i)L[i][c%10]=i+1,R[i][c%10]=i-1;
		for(i=1;i<=n;++i){//枚举断点k
			if(c>=a[i]){
				L[R[i+1][(c-a[i])%10]][c%10]=min(L[R[i+1][(c-a[i])%10]][c%10],L[i-1][(c-a[i])%10]);
				R[L[i-1][(c-a[i])%10]][c%10]=max(R[L[i-1][(c-a[i])%10]][c%10],R[i+1][(c-a[i])%10]);
			}
		}
		for(i=2;i<=n;++i)R[i][c%10]=max(R[i][c%10],R[i-1][c%10]);
		for(i=n-1;i;--i)L[i][c%10]=min(L[i][c%10],L[i+1][c%10]);
		if(L[n][c%10]<=1||R[1][c%10]>=n)return c;
	}
}
int T;
int main(){
	scanf("%d",&T);
	for(int z=1;z<=T;++z)printf("Case #%d: %d\n",z,work());
	return 0;
}