#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rng(int l, int r) { return rnd() % (r - l + 1) + l; }
#define rep(i, a, b) for (int i = (a), I = (b); i <= I; ++i)
#define per(i, a, b) for (int i = (a), I = (b); i >= I; --i)
using i64 = long long;
using i128 = __int128_t;
template<typename T> void up(T &x, T y) { if (x < y) x = y; }
template<typename T> void down(T &x, T y) { if (x > y) x = y; }

string s;
int n, m;
i128 ans;
i128 msk0, msk1, all;

bool match(int x, int y) {
    return s[x] == '?' || s[x] == '0' + y;
}
void check(i128 x) {
    x *= x;
    if ((x & msk0) || ((all ^ x) & msk1)) return;
    ans = x;
}
i128 get_sqr(i128 x) {
    return sqrt((long double) x);
}

void dfs(int pos, i128 cur) {
    if (~ans) return;
    if (pos == m - 1) {
        i128 p = get_sqr(cur);
        while (p * p < cur) ++p;
        while (((p * p) >> m) == (cur >> m)) check(p++);
        return;
    }
    if (match(pos, 0)) dfs(pos - 1, cur);
    if (match(pos, 1)) dfs(pos - 1, cur | i128(1) << pos);
}

void dfs(int pos, i128 cur, i128 sqr) {    
    if (~ans) return;
    if (pos == m) {
        check(sqr);
        check(sqr | i128(1) << (pos - 1));
        return;
    }
    int tmp = (sqr * sqr) >> pos & 1;
    rep(k, 0, 1) {
        int val = tmp + k + k * (pos == 2);
        if (match(pos, val & 1)) dfs(pos + 1, cur | i128(val & 1) << pos, sqr | i128(k) << (pos - 1));
    }
}

void solve() {
    n = s.size();
    m = (n + 1) / 2;
    int cnt_left = count(s.begin(), s.begin() + m, '?');
    int cnt_right = count(s.begin() + m, s.end(), '?');
    msk0 = msk1 = all = 0;
    rep(i, 0, n - 1) {
        all |= i128(1) << i; 
        if (s[i] == '?') continue;
        (s[i] == '0' ? msk0 : msk1) |= i128(1) << i;
    }

    if (cnt_left < cnt_right) {
        dfs(2, 1, 1);
    } else {
        dfs(n - 1, 0);
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    int T;
    cin >> T;
    rep(t, 1, T) {
        cin >> s;
        reverse(s.begin(), s.end());
        ans = -1;
        for (int c = 0; ; c += 2) {
            if (match(0, 1)) { 
                s[0] = '1';
                solve();
                if (~ans) {
                    cout << "Case #" << t << ": ";
                    per(i, n - 1, 0) cout << int(ans >> i & 1);
                    rep(i, 0, c - 1) cout << 0;
                    cout << "\n";
                    break;
                }
            }
            s.erase(s.begin());
            s.erase(s.begin());
        }
    }

    return 0;
}