#include <bits/stdc++.h>

using i64 = long long;

const int N = 1E6 + 5;

int n;
std::string s;
int a[N];
int L[10][N], R[10][N];
// int f[300][300];

void solve() {
	std::cin >> s;
	n = s.length();
	
	for (int i = 1; i <= n; i++) {
		a[i] = s[i - 1] - '0';
		// f[i][i] = a[i];
	}

	// for (int i = 1; i < n; i++) {
	// 	f[i][i + 1] = a[i] + a[i + 1];
	// }

	// for (int len = 3; len <= n; len++) {
	// 	for (int l = 1, r = len; r <= n; ++l, ++r) {
	// 		f[l][r] = 1E9;
	// 		for (int k = l + 1; k < r; k++) {
	// 			f[l][r] = std::min(f[l][r], a[k] + std::max(f[l][k - 1], f[k + 1][r]));
	// 		}
	// 	}
	// }

	// for (int i = 1; i <= n; i++) {
	// 	for (int j = i + 1; j <= n; j++) {
	// 		std::cerr << f[i][j] << " ";
	// 	}
	// 	std::cerr << "\n";
	// }

	// std::cerr << f[1][n] << "\n";

	int ans = 1E9;
	for (int c = 0; c <= 180; c++) {
		int now = c % 10;
		for (int i = 0; i <= n + 1; i++) {
			L[now][i] = i + 1;
			R[now][i] = i - 1;
		}

		for (int i = 1; i <= n; i++) {
			if (a[i] <= now) {
				int x = L[(now - a[i]) % 10][i - 1], y = R[(now - a[i]) % 10][i + 1];
				L[now][y] = std::min(L[now][y], x);
				R[now][x] = std::max(R[now][x], y);
			}
		}

		for (int i = n; i >= 1; i--) {
			L[now][i] = std::min(L[now][i], L[now][i + 1]);
		}
		
		for (int i = 1; i <= n; i++) {
			R[now][i] = std::max(R[now][i], R[now][i - 1]);
		}

		for (int i = 1; i <= n; i++) {
			if (L[now][i - 1] <= 1 && R[now][i + 1] >= n) {
				ans = std::min(ans, c + a[i]);
			}
		}
	}

	std::cout << ans << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin >> T;

	for (int i = 1; i <= T; i++) {
		std::cout << "Case #" << i << ": ";
		solve(); 
	}
	return 0;
}