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

using ll = long long;
constexpr int N = 1e5 + 5, M = 70;

int n, f[N][M]; char w[N];

struct Fenwick {
	int t[N];
	void clear() {memset(t + 1, 0, n + 1 << 2);}
	void update(int p, int v) {
		if(!p) return;
		while(p <= n) {t[p] = max(t[p], v), p += p & -p;}
	}
	int query(int p) {
		int tmp = 0;
		while(p >= 1) {tmp = max(t[p], tmp), p -= p & -p;}
		return tmp;
	}
} T[M][10];

void solve(int Case) {
	scanf("%s", w + 1), n = strlen(w + 1);
	for(int i = 1; i < M; ++ i) {
		for(int j = 1; j <= 9; ++ j) T[i][j].clear();
	}
	for(int i = n; i; -- i) {
		w[i] -= '0';
		for(int v = 1; v < w[i]; ++ v) f[i][v] = 0;
		for(int v = w[i]; v < M; ++ v) {
			f[i][v] = i;
			T[v][w[i]].update(i - 1, f[i + 1][v - w[i]]);
		}
	}
	for(int l = n; l; -- l) {
		for(int v = 1; v < M; ++ v) {
			for(int w = 1; w <= min(v, 9); ++ w) {
				f[l][v] = max(f[l][v], T[v][w].query(f[l][v - w])); 
			}
		}
		for(int v = w[l]; v < M; ++ v) {
			T[v][w[l]].update(l - 1, f[l + 1][v - w[l]]);
		}
	}
	for(int i = 1; i < M; ++ i) {
		if(f[1][i] == n) return void(printf("Case #%d: %d\n", Case, i));
	}
}

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