// Code by Heratino & Nelofus
// 泣いていたって空は晴れるよ
#include <bits/stdc++.h>
using i64 = long long;

//{{{
template<typename Ta, typename Tb>
inline void chkmax(Ta &a, const Tb &b) {if (a < b)	a = b;}
template<typename Ta, typename Tb>
inline void chkmin(Ta &a, const Tb &b) {if (a > b)	a = b;}
//}}}

constexpr int N = 1e6 + 10;
constexpr int M = 185;

int f[N][M], c[N];
int lst[N][10];
int n;
std::string s;

int main() {
#ifdef HeratinoNelofus
	freopen("input.txt", "r", stdin);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin >> T;
	for (int _ = 1; _ <= T; _++) {
		std::cin >> s;
		n = s.length();
		s = ' ' + s;
		for (int i = 1; i <= n; i++)
			c[i] = s[i] - '0';
		for (int i = 1; i <= n; i++)
			memcpy(lst[i], lst[i - 1], sizeof(lst[i])), lst[i][c[i]] = i;
		for (int i = 0; i < M; i++)
			f[n][i] = n + 1;
		for (int l = n - 1; l >= 0; l--) {
			f[l][0] = l + 1;
			for (int v = 1; v < M; v++) {
				f[l][v] = f[l][v - 1];
				if (f[l][v] == n + 1)
					continue;
				for (int cx = 1; cx <= 9 && cx <= v; cx++) {
					int p = f[l][v - cx];
					int q = lst[p][cx];
					if (q < l)	continue;
					chkmax(f[l][v], f[q][v - cx]);
				}
			}
		}
		for (int i = 0; i < M; i++)
			if (f[0][i] == n + 1) {
				std::cout << "Case #" << _ << ": " << i << '\n';
				break;
			}
	}
	return 0;
}