#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;
	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[k][i] = max(R[k][i], R[k][i - 1]);
		if(R[k][0] > n && L[k][n + 1] < 1) break;
		++ ans;
		if(++ k == 10) k = 0;
	}
	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;
}