/**
 * @author : cyb1010
 * @date   : 2024-05-06 10:23:57
 * @file   : grow.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef __uint128_t U;
U val, msk, UP;
int __, n, g[60], tot, N, A;
char s[130];
bool perf1(U dw) {
    U l = sqrtl(dw), x;
    while ((x = l * l) <= UP) {
        if ((x ^ dw) & msk) {
            l++;
            continue;
        }
        for (int i = n - 1; ~i; i--) putchar((x >> i & 1) + '0');
        while (A--) putchar('0');
        putchar('\n');
        return true;
    }
    return false;
}
bool perf2() {
    U T = s[n - 1] - '0', x = 0, M = 0;
    for (int i = 1; i < N; i++) {
        T |= (s[n - i - 1] - '0') << i, M = M << 1 | 1;
        if (((x * x) ^ T) & M) x += (U)1 << (i - 1);
    }
    x += (U)1 << N - 1;
    x *= x;
    if ((x ^ val) & msk) return false;
    for (int i = n - 1; ~i; i--) putchar((x >> i & 1) + '0');
    while (A--) putchar('0');
    putchar('\n');
    return true;
}
void work() {
    scanf("%s", s), n = strlen(s), A = 0;
    while (s[n - 1] == '0') n -= 2, A += 2;
    while (true) {
        s[n - 1] = '1';
        N = (n + 1) / 2, tot = 0;
        msk = val = UP = 0;
        for (int i = 0; i < n; i++) {
            msk <<= 1, val <<= 1, UP <<= 1;
            if (s[i] == '?')
                g[tot++] = i, UP |= 1;
            else
                msk |= 1, val |= (s[i] - '0'), UP |= (s[i] - '0');
        }
        if (!tot) {
            printf("%s", s);
            while (A--) putchar('0');
            putchar('\n');
            return;
        }
        int cnt = (tot + 1) / 2;
        if (g[cnt] >= N) {
            int M = 1 << cnt;
            for (int i = 0; i < M; i++) {
                U tmp = val;
                for (int j = 0; j < cnt; j++) tmp |= (i >> j & 1) << g[j];
                if (perf1(tmp)) return;
            }
        } else {
            int M = 1 << cnt;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < cnt; j++)
                    s[g[tot - j - 1]] = '0' + (i >> j & 1);
                if (perf2()) return;
            }
        }
        n -= 2, A += 2;
    }
}
int main() {
    // fo("grow");
    // work();
    int _;
    scanf("%d", &_);
    for (int i = 1; i <= _; i++) printf("Case #%d: ", i), work();
    return 0 ^ __ ^ 0;
}