#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;

int n, mid;
string str;
i128 ans, mask0, mask1, tot;

void dfs1(int idx, i128 val, i128 s) {
    if(ans != -1) return;
    
    if(idx == mid) {
        if(!(((s * s) & mask0) || ((tot ^ (s * s)) & mask1))) {
            ans = s * s;
        }
        if(!((((s | (i128)1 << (idx - 1)) * (s | (i128)1 << (idx - 1))) & mask0) || ((tot ^ ((s | (i128)1 << (idx - 1)) * (s | (i128)1 << (idx - 1)))) & mask1))) {
            ans = (s | (i128)1 << (idx - 1)) * (s | (i128)1 << (idx - 1));
        }
        return;
    }
    
    int flag = ((s * s) >> idx) & 1;
    int next = flag;
    if(str[idx] == '?' || str[idx] == ('0' + (next & 1))) {
        dfs1(idx + 1, val | (i128)(next & 1) << idx, s);
    }
    next = flag + 1;
    if(idx == 2) ++next;
    if(str[idx] == '?' || str[idx] == ('0' + (next & 1))) {
        dfs1(idx + 1, val | (i128)(next & 1) << idx, s | i128(1) << (idx - 1));
    }
}

void dfs2(int idx, i128 val) {
    if(ans != -1) return;
    if(idx == mid - 1) {
        i128 x = sqrt((long double) val);
        while(x * x < val) ++x;
        while(((x * x) >> mid) == (val >> mid)) {
            if(!(((x * x) & mask0) || ((tot ^ (x * x)) & mask1))) {
                ans = x * x;
                break;
            }
            ++x;
        }
        return;
    }
    
    if(str[idx] == '?' || str[idx] == '0') dfs2(idx - 1, val);
    if(str[idx] == '?' || str[idx] == '1') dfs2(idx - 1, val | (i128)1 << idx);
}

void solve(int t) {
    cin >> str; reverse(str.begin(), str.end());
    ans = -1;
    int i = 0;
    while(str.size()) {
        if(str[0] == '?' || str[0] == '1') {
            str[0] = '1';
            
            mid = (str.size() + 1) / 2;
            int lcnt = 0, rcnt = 0;
            for(int i = 0; i < mid; ++i) lcnt += str[i] == '?';
            for(int i = mid; i < str.size(); ++i) rcnt += str[i] == '?';
            
            mask0 = mask1 = tot = 0;
            for(int i = 0; i < str.size(); ++i) {
                tot |= ((i128)1 << i);
                if(str[i] == '?') continue;
                if(str[i] == '0') mask0 |= ((i128)1 << i);
                if(str[i] == '1') mask1 |= ((i128)1 << i);
            }
            
            if(lcnt < rcnt) {
                // cout << "a" << endl;
                dfs1(2, 1, 1);
            }
            else {
                // cout << "b" << endl;
                dfs2(str.size() - 1, 0);
            }
            
            if(ans != (i128)-1) {
                cout << "Case #" << t << ": ";
                for(int i = str.size() - 1; i >= 0; --i) cout << (long long)((ans >> i) & 1);
                for(int j = 1; j <= i; ++j) cout << '0';
                cout << "\n"; break;
            }
            // cout << (long long)ans << endl;
        }
        str.erase(str.begin()); str.erase(str.begin());
        i += 2;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int t, tot; cin >> t; tot = t;
    while(t--) solve(tot - t);
    return 0;
}