/**
 * 感觉题目很莫名啊，一开始以为是要一个非传统题，然后发现是个传统题就宕机了。
 * 其实题目本身是很合理的，因为确实可以做 doge。
 * 考虑一个暴力 dp，设 dp[l,r] 表示在 [l,r] 上查找的答案。
 * 那么枚举我们用的 mid=k，则 dp[l,r]=min(c[k]+max(dp[l,k-1],dp[k+1,r]))。
 * 看起来不像能优化了，但是发现很有趣的事情是给了值域 <=9。
 * 这是个什么意思？就是说我们直接乱二分，答案都不超 9*lg。
 * 那还说个屁啊！直接从值域上做。
 * 显然地大区间包含小区间，于是 dp[l,r]<=dp[l',r']，l'<=l<=r<=r'，因此直接维护分界点。
 * 设一个 L[v,r] 表示 r 结尾，答案不超过 v，l 往前最多到哪，同理有 R[v,l]。
 * 将 v 从小到大地考虑，每次尝试用枚举得到的 c[x] 作为 mid 来扩展。
 * 那么 c[x] 能对应到的 l 至少是 L[v-c[x],x-1]，对应到的 r 至多是 R[v-c[x],x+1]。
 * 也就是说 L[v-c[x],x-1]~R[v-c[x],x+1] 这个区间内的 L[v],R[v] 都可以更新为这俩值。
 * 大力飞砖的话可以上线段树直接区间覆盖，不过我们没什么时间写 DS。
 * 你注意我们有单调性，于是 L[v-c[x],x-1] 到结束的位置 i，都可以更新 R[v,i] 和 R[v-c[x],x+1] 取 max。
 * 那扫就完了！
 * 一个问题是空间不够，但是注意到这个值域下只考虑最低位是哪个是不会重的，于是用一种另类的滚动即可。
 */
#include <algorithm>
#include <cstdio>
using i32 = int;
constexpr i32 N = 1E6;
i32 n;
char s[N + 5];
i32 L[10][N + 2], R[10][N + 2];
i32 solve() noexcept {
	scanf("%s", s + 1), n = __builtin_strlen(s + 1);
	for (i32 i = 1; i <= n; ++i) s[i] &= 15;
	auto init = [](auto L, auto R) noexcept {
		for (i32 i = 0; i <= n + 1; ++i) L[i] = i + 1, R[i] = i - 1;
	};
	init(L[0], R[0]);
	for (i32 v = 1;; ++v) {
		i32 p = v % 10;
		init(L[p], R[p]);
		for (i32 i = 1; i <= n; ++i)
			if (v >= s[i]) {
				i32 q = (p + 10 - s[i]) % 10, l = L[q][i - 1], r = R[q][i + 1];
				L[p][r] = std::min(L[p][r], l), R[p][l] = std::max(R[p][l], r);
			}
		for (i32 i = n - 1; i; --i) L[p][i] = std::min(L[p][i], L[p][i + 1]);
		for (i32 i = 2; i <= n; ++i) R[p][i] = std::max(R[p][i], R[p][i - 1]);
		if (L[p][n] <= 1 || R[p][1] >= n) return v;
	}
	return -1;
}
signed main() noexcept {
	i32 Test, Case = 1;
	for (scanf("%d", &Test); Case <= Test; ++Case) printf("Case #%d: %d\n", Case, solve());
	return 0;
}