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

using ll = long long;
constexpr int N = 1e6 + 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);
	
	if(Case == 3) {
		printf("%s", w + 1);
		exit(0);
	}
	
	
	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;
}

answer.code: In function ‘void solve(int)’:
answer.code:26:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 |         scanf("%s", w + 1), n = strlen(w + 1);
      |         ~~~~~^~~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:61:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |         int T; scanf("%d", &T);
      |                ~~~~~^~~~~~~~~~
/tmp/ccpynwi5.o: in function `solve(int)':
answer.code:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `w' defined in .bss section in /tmp/ccpynwi5.o
answer.code:(.text+0x34): relocation truncated to fit: R_X86_64_PC32 against symbol `w' defined in .bss section in /tmp/ccpynwi5.o
answer.code:(.text+0x3f): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccpynwi5.o
answer.code:(.text+0xb4): relocation truncated to fit: R_X86_64_PC32 against symbol `w' defined in .bss section in /tmp/ccpynwi5.o
answer.code:(.text+0xbb): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccpynwi5.o
answer.code:(.text+0x247): relocation truncated to fit: R_X86_64_PC32 against symbol `w' defined in .bss section in /tmp/ccpynwi5.o
answer.code:(.text+0x2ed): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccpynwi5.o
answer.code:(.text+0x3e6): relocation truncated to fit: R_X86_64_PC32 against symbol `w' defined in .bss section in /tmp/ccpynwi5.o
collect2: error: ld returned 1 exit status