/*
这一道题的难点在于怎么确定方案。

如果对半分肯定是最优的。如果不考虑权值的话。

但是问题就是需要考虑权值。有什么特殊的性质吗？

肯定只能考虑 dp 嘛。

而且这种 dp 应该算是很经典的。就是直接区间 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}\le 9$ 可以好好利用一下。

整个 dp 的值必然小于 $c\log n$。因为直接二分的话可以获得这个大小的值。

所以可以考虑放在值域上做一下。而且这个很具有单调性。

因为 $f_{i,j}\le f_{i,k}$ 吧。因为你可以跟着选。

那么可以设计一个 dp 就是说 $L_{v,j}$ 表示最小的 $i$ 满足 $f_{i,j}\le v$。

同理设计出 $R_{v,i}$。

然后考虑怎么将这个转移出来。这下的话可以考虑将 $v$ 从小到大来考虑。

假如说一个区间 $[i,j]$ 使得 $f_{i,j}\le v$。那么一定存在一个断点 $x$

满足 $f_{i,x-1}\le v-c_{x}$ 且 $f_{x+1,j}\le v-c_{x}$。

这样的话可以考虑枚举断点来转移。假设前面的 $v$ 都处理好了。

用 $x$ 可以更新 $[L_{v-a_{x},x-1},R_{v-a_{x},x+1}]$ 这个区间的 $L_{v}$ 和 $R_{v}$。

根据单调性可以这样转移出来。  

这样的时间复杂度是 $O(nc\log n)$ 的。但是空间还是会寄掉。可以滚动一下。因为只需要 $c$ 的空间容量。

*/
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
	int s=0,w=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';
	return s*w;
}
const int N=1e6+5;
char a[N];int T,n,c[N];
int L[10][N],R[10][N];
inline int solve(){
	scanf("%s",a+1);
	n=strlen(a+1);
	for(int i=1;i<=n;++i)c[i]=a[i]-'0';
	for(int v=0;v<=181;++v){
		int F=v%10; 
		for(int i=0;i<=n+1;++i)L[F][i]=i+1,R[F][i]=i-1;
		for(int i=1;i<=n;++i){
			if(v<c[i])continue;
			int x=L[(v-c[i])%10][i-1],y=R[(v-c[i])%10][i+1];
			L[F][y]=min(L[F][y],x);R[F][x]=max(R[F][x],y);
		}
		for(int i=2;i<=n;++i)R[F][i]=max(R[F][i-1],R[F][i]);
		for(int i=n-1;i;--i)L[F][i]=min(L[F][i+1],L[F][i]);
		if(L[F][n]<=1||R[F][1]>=n)return v;
	}
}

int main(){
	T=rd();
	for(int i=1;i<=T;++i)printf("Case #%d: %d\n",i,solve());
	return 0;
}