/* 陽炎は黄泉に待たむと。*/

#include <bits/stdc++.h>
using namespace std;

#define inl inline
constexpr int BUF = 1<<19;
char ibuf[BUF], *__st, *__ed;
inl void buffer () { __st = ibuf,
	__ed = ibuf + fread (ibuf, 1, BUF, stdin); }
inl char getc () {
	return __st == __ed && (buffer (),
		__st == __ed) ? EOF : *__st++; }
inl int read (char *s) {
	static char c = getc ();
	for (; ~c && isspace (c); c = getc ());
	if (c == EOF) return 0; int len = 0;
	for (; ~c && !isspace (c); c = getc ())
		*s++ = c, ++len; return *s = 0, len;
}

typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) begin (p), end (p)
#define empb emplace_back

#ifdef SHIKEN
#define msg(args...) fprintf (stderr, args)
#else
#define msg(...) void ()
#endif

constexpr int N = 1e6 + 10, INF = 0x3f3f3f3f;
int _lbd[10][N], _rbd[10][N], T, n, f[N], g[N]; char a[N];

inl void gomn (int &x, int y) { if (x > y) x = y; }
inl void gomx (int &x, int y) { if (x < y) x = y; }

int main () {
	/*  */
int *lbd[200], *rbd[200];
for (int i = 0; i < 200; ++i)
	lbd[i] = _lbd[i % 10],
	rbd[i] = _rbd[i % 10];

scanf ("%d", &T);
for (int t = 1; t <= T; ++t) {
	n = read (a + 1); int c = 0, ans = INF;
	memset (_lbd, 0x3f, sizeof _lbd);
	memset (_rbd, ~0x3f, sizeof _rbd);
	for (int i = 1; i <= n; ++i)
		a[i] -= '0', f[i] = g[i] = i;
	while (c < ans) {
		for (int i = 1, r = rbd[c][0]; i <= n; ++i) {
			if (rbd[c][i] > r) r = rbd[c][i];
			if (g[i] < r) g[i] = r;
		}
		int s = 0;
		for (int i = n, l = lbd[c][n + 1]; i; --i) {
			if (lbd[c][i] < l) l = lbd[c][i];
			if (l < f[i]) f[i] = l;
			s |= (f[i] == 1 && g[i] == n)<<a[i];
		}
		ans = min (ans, __builtin_ctz (s) + c);
		for (int i = 1; i <= n; ++i) {
			gomn (lbd[c + a[i]][g[i] + 1], f[i]);
			gomx (rbd[c + a[i]][f[i] - 1], g[i]);
		}
		memset (lbd[c], 0x3f, sizeof _lbd[0]);
		memset (rbd[c], ~0x3f, sizeof _rbd[0]);
		++c;
	}
	printf ("Case #%d: %d\n", t, ans);
}

	return 0;
}