#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;

using ll = long long;
constexpr int N = 1e6 + 5;

int n, L[10][N], R[10][N];
char w[N];

void solve(int Case) {
	scanf("%s", w + 1);
	n = strlen(w + 1);
	for(int i = 1; i <= n; ++ i) {
		w[i] -= '0';
	}
	int ans = 0, k = 0, t;
	while(1) {
		for(int i = 0; i <= n + 1; ++ i) L[k][i] = i - 1, R[k][i] = i + 1;
		for(int i = 1, j, l, r; i <= n; ++ i) {
			if(ans >= w[i]) {
				j = (ans - w[i]) % 10, l = L[j][i], r = R[j][i];
				L[k][r] = min(L[k][r], l);
				R[k][l] = max(R[k][l], r);
			}
		}
		for(int i = n; i >= 0; -- i) L[k][i] = min(L[k][i], L[k][i + 1]);
		for(int i = 1; i <= n + 1; ++ i) R[i][k] = max(R[k][i], R[k][i - 1]);
		
		if(R[k][0] > n && L[k][n + 1] < 1) break;
		
		t = k, ++ ans;
		if(++ k == 10) k = 0;
		
		memcpy(L[k], L[t], n + 1 << 2);
		memcpy(R[k], R[t], n + 1 << 2);
	}
	printf("Case #%d: %d\n", Case, ans);
}

int main() {
	int T; scanf("%d", &T);
	for(int i = 1; i <= T; ++ i) solve(i);
	return 0;
}