#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
using i128 = __int128;
const int mod = 1000000007;
const int N = 127;
const int LOG = 20;
const ll inf = 9e18;
const double eps = 1e-11;
i128 p[N];
vector<i128> cand;
void solvel(vector<int> a, int pow2) {
    int n = a.size(), m = (n + 1) / 2;
    i128 x = 0;
    vector<int> pos;
    for (int i = 0; i < n; i++) {
        int v = a[i];
        if (a[i] == -1) {
            v = (i < n - m ? 1 : 0);
            if (i >= n - m) pos.push_back(i);
        }
        
        x += v * p[i];
    }
    
    int sz = pos.size(), k = (1 << sz);
    for (int mask = 0; mask < k; mask++) {
        i128 test = x;
        for (int i = 0; i < sz; i++) {
            if (!((mask >> i) & 1)) continue;
            test += p[pos[i]];
        }
        
        i128 l = 0, r = inf, sq = 0;
        while (l <= r) {
            i128 mid = (l + r) / 2;
            if (mid * mid <= test) l = mid + 1, sq = mid;
            else r = mid - 1; 
        }
        
        cand.push_back(sq * p[pow2]);
    }
}

void solver(vector<int> a, int pow2) {
    int n = a.size(), m = (n + 1) / 2;
    vector<int> pos;
    for (int i = 0; i <= m; i++) {
        if (a[i] == -1) pos.push_back(i);
    }
    
    int sz = pos.size(), k = (1 << sz);
    for (int mask = 0; mask < k; mask++) {
        vector<int> b = a;
        for (int i = 0; i < sz; i++) {
            int bit = (mask >> i) & 1;
            b[pos[i]] = bit;
        }
        
        i128 x = 0;
        for (int i = 0; i <= m; i++) {
            x += b[i] * p[i];
        }
        
        for (int s = 1; s < 4; s += 2) {
            i128 cur = s;
            for (int i = 3; i <= m; i++) {
                i128 test = x % p[i + 1];
                i128 deg1 = p[i] * cur % p[i + 1], deg0 = cur * cur % p[i + 1];
                if (deg0 != test) cur += p[i - 1];
            }
            
            cand.push_back(cur * p[pow2]);
        }
    }
}

void dfs(vector<int> a, int pow2) {
    int n = a.size(), m = (n + 1) / 2;
    if (n < 3) {
        solvel(a, pow2);
        return;
    }
    
    if (a[0] == -1) {
        for (int i = 0; i < 2; i++) {
            vector<int> b = a;
            b[0] = i;
            dfs(b, pow2);
        }
        
        return;
    }
    
    if (a[0] == 0) {
        reverse(a.begin(), a.end());
        a.pop_back();
        a.pop_back();
        reverse(a.begin(), a.end());
        dfs(a, pow2 + 1);    
        return;
    }
    
    int cntl = 0, cntr = 0;
    for (int i = 0; i <= m; i++) {
        if (a[i] == -1) cntr++;
    }
    
    for (int i = n - m; i < n; i++) {
        if (a[i] == -1) cntl++;
    }
    
    if (cntl <= cntr) solvel(a, pow2);
    else solver(a, pow2);
}

string s;
int n, m, k, qq;
void solve() {
    cand.clear();
    cin >> s;
    n = s.size();
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = s[i] - '0';
        if (s[i] == '?') a[i] = -1;
    }
    
    reverse(a.begin(), a.end());
    dfs(a, 0);
    sort(cand.begin(), cand.end());
    i128 res = -1;
    int sz = cand.size();
    for (int i = 0; i < sz; i++) {
        if (i != 0 && cand[i] == cand[i - 1]) continue;
        i128 x = cand[i] * cand[i];
        i128 temp = x;
        bool ok = 1;
        for (int j = 0; j < n; j++) {
            if ((x & 1) != a[j] && a[j] != -1) ok = 0;
            x >>= 1;
        }
        
        if (ok) res = temp;
    }   
    
    assert(res != -1);
    vector<int> out;
    while (res != 0) {
        out.push_back(res & 1);
        res >>= 1;    
    }
    
    reverse(out.begin(), out.end());
    for (int x : out) {
        cout << x;    
    }
    
    cout << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    p[0] = 1;
    for (int i = 1; i < N; i++) {
        p[i] = p[i - 1] * 2;
    }
    
    int tt;
    cin >> tt;
    for (int i = 1; i <= tt; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
}