#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[maxn][10], mxr[maxn][10], a[maxn];
char s[maxn];
void init(int p) {
    for (int i = 0; i <= n + 1; ++i) mnl[i][p] = i + 1, mxr[i][p] = 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[i - 1][q], r = mxr[i + 1][q];
            mnl[r][p] = min(mnl[r][p], l);
            mxr[l][p] = max(mxr[l][p], r);
        }
        for (int i = 2; i <= n; ++i) mxr[i][p] = max(mxr[i][p], mxr[i - 1][p]);
        for (int i = n - 1; i >= 1; --i) mnl[i][p] = min(mnl[i][p], mnl[i + 1][p]);
        if (mxr[1][p] >= n || mnl[n][p] <= 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;
}