/*
如果所有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[10][N],R[10][N];
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<181;++c){
		int zj=c%10;
		for(i=0;i<=n+1;++i)L[zj][i]=i+1,R[zj][i]=i-1;
		for(i=1;i<=n;++i){//枚举断点k
			if(c>=a[i]){
				int x=R[(c-a[i])%10][i+1],y=L[(c-a[i])%10][i-1];
				L[zj][x]=min(L[zj][x],y);
				R[zj][y]=max(R[zj][y],x);
			}
		}
		for(i=2;i<=n;++i)R[zj][i]=max(R[zj][i],R[zj][i-1]);
		for(i=n-1;i;--i)L[zj][i]=min(L[zj][i],L[zj][i+1]);
		if(L[zj][n]<=1||R[zj][1]>=n)return c;
	}
	puts("Didn't find the answer.");
	assert(0);
}
int T;
int main(){
	scanf("%d",&T);
	for(int z=1;z<=T;++z)printf("Case #%d: %d\n",z,work());
	return 0;
}