#include<bits/stdc++.h>
using namespace std;
int mian(); int main() { return mian(); }

const int N = 1e6 + 16;
int n, c[N];
int L[N][11], R[N][11];
int ml[N], mr[N];
char chs[N];
void solve() {
	scanf("%s", chs + 1); n = strlen(chs + 1);
	for(int i = 1; i <= n; ++i) {
		c[i] = chs[i] - '0';
		mr[i] = L[i][0] = i + 1; ml[i] = R[i][0] = i - 1;
	}
	L[n + 1][0] = n + 2; R[n + 1][0] = n;
	for(int i = 0; i <= 10; ++i) L[0][i] = 1, R[0][i] = -1;
	for(int j = 1; j <= 180; ++j) {
		int now = j % 10;
		for(int i = 1; i <= n; ++i) {
			if(c[i] > j) continue;
			const int nd =( ( j - c[i] ) % 10 + 10 ) % 10, l = L[i - 1][nd], r = R[i + 1][nd];
			//cout<<i<<" "<<l<<" "<<r<<endl;
			mr[r] = min(mr[r], l); ml[l] = max(ml[l], r);
		}
		for(int i = n, mic = n + 1; i >= 1; --i) {
			mic = min(mic, mr[i]); mr[i] = i + 1;
			L[i][now] = mic;
		}
		for(int i = 1, mic = 0; i <= n; ++i) {
			mic = max(mic, ml[i]); ml[i] = i - 1;
			R[i][now] = mic;
		} 
		//for(int i = 1; i <= n; ++i) cout<<L[i][now]<<" ";; puts("");
		//for(int i = 1; i <= n; ++i) cout<<R[i][now]<<" ";; puts("\n");
		if(R[1][now] >= n) return printf("%d\n", j), void();
	}
}
int mian() {
	int T; scanf("%d", &T);
	for(int tim = 1; tim <= T; ++tim) {
		printf("Case #%d: ", tim);
		solve();
	}
	return 0;
}/*
1
1111119

4
111
1111
1111111
1111119

给定一个长度为 $n$ 的序列 $c$。对于一个 $x$，可以花费 $c_i$ 的代价，得到 $x$ 与 $i$ 的关系
假设当前所在区间为 $[l,r]$，那么询问完成之后，$x$ 可能在的区间会变为 $[l,i),[i,i],(i,r]$
如果 $l=r$，那么就找到了 $x=l$
输出要找到一个 $x$，在最坏的情况下（即在策略优秀的情况下），最小的查找次数
$n\le 10^6,1\le c_i\le 9$
$480s, 1G$

首先可以直接根据题意得到一个 $dp$ 为 $dp_{l,r}$ 表示区间 $[l,r]$ 所需的最小代价
转移就是 $dp_{l,r}=\min c_k+\max(dp_{l,k-1}, dp_{k+1,r})$
注意到这个 $c$ 特别小，那么启示可能需要在 $dp$ 的转移过程中增加一个 $c$
比如可以设计 $dp_{l,r,c}$ 表示当前的区间为 $[l,r]$，分割点的权值为 $c$ 的最小代价
那么如果可以预处理的话那么这里就还是十分优秀的
注意到因为区间是取 $max$，而且一个区间越大肯定花费越大
hint:考虑答案上界，那么就是直接正常二分，那么此时最大的花费也只会有 $180$
那么，根据刚才的性质，我们可以想到，在固定左端点的情况下，右端点一定会随着越来越大而使得 $dp$ 值越来越大
那么设计 $dp_{i,j}$ 表示当前的左端点为 $i$，区间 $dp$ 值为 $j$ 的右端点的最远位置
可以考虑这样，因为要是两端区间拼接起来，那么假设另个区间的左端点是 $k$
那么两段的区间就会是 $[i,k-1)$ 和 $[k,dp_{k}]$
枚举一个 $t$ 表示前一段区间的 $dp$ 值，那么这里就会是 $dp_{i,j}=\max_{k-2\le dp_{i,t}} dp[k][j - c_{k-1}], \max [ c [ dp_{i,t} + 1 ] + t = j]dp_{ dp_{i,t} + 2, less than j}$

换一个思路，考虑不从区间左端点下手，从区间分割点下手
那么考虑从小到大枚举每一个 $j$ ，然后考虑维护一个 $L_{i,x},R_{i,x}$ 表示当前点是 $i$，满足 $dp[k][i]=x$ 的最小的 $k$ 以及在右侧的最大
那么，那么如果可以得到这个东西，那么就可以得到一个区间 $[L_i,R_i]$ 使得这个区间中的所有区间最大都不会超过 $j$
那么，现在要考虑求出 $L_i$，那么根据已经得到的这些，那么唯一需要根新的就是 $L_{i,j}$
那么对于每一个点 $i$，找到所有覆盖当前点的区间中，最小的一个左端点就会是 $L_{i,j}$
可以看成所有右端点在其右侧区间，因为如果左端点也比当前点更大的话那么一定不如直接选择当前着一个点
结束条件就是 $L_{n,j}=1$，因为 $j$ 只会有 $j-c_i$ 的范围个，那么记录一个 $now$ 表示当前的 $j$ 应该存到哪里，然后每一次 $now+1%10$
查询就是 $now-c_i+10%10$，存在 $now$ 的位置。其中 $now$ 可以发现就是 $j%10$
了注意到当区间里面只有一个数字的时候也需要花费
*/