#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;

const int maxn = 1e6 + 10;
int n, mnl[10][maxn], mxr[10][maxn], a[maxn];
char s[maxn];
void init(int p) {
    for (int i = 0; i <= n + 1; ++i) mnl[p][i] = i + 1, mxr[p][i] = i - 1;
}
void work() {
    scanf("%s", s + 1), n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) a[i] = s[i] - '0';
    memset(mnl, 0, sizeof mnl);
    memset(mxr, 0, sizeof mxr);
    init(0);
    for (int x = 1; ; ++x) {
        int p = x % 10;
        init(p);
        for (int i = 1; i <= n; ++i) if (x >= a[i]) {
            int q = (x + 10 - a[i]) % 10;
            int l = mnl[q][i - 1], r = mxr[q][i + 1];
            mnl[p][r] = min(mnl[p][r], l);
            mxr[p][l] = max(mxr[p][l], r);
        }
        for (int i = 2; i <= n; ++i) mxr[p][i] = max(mxr[p][i], mxr[p][i - 1]);
        for (int i = n - 1; i >= 1; --i) mnl[p][i] = min(mnl[p][i], mnl[p][i + 1]);
        if (mxr[p][1] >= n || mnl[p][n] <= 1)
            return printf("%d\n", x), void();
    }
}

int main() {
    int T; scanf("%d", &T);
    for (int i = 1; i <= T; ++i) printf("Case #%d: ", i), work();
    return 0;
}