#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 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;

bool match(int x, int y) {
    return s[x] == '?' || s[x] == '0' + y;
}
void check(i128 x) {
    x *= x;
    rep(i, 0, n - 1) if (!match(i, x >> i & 1)) return;
    ans = x;
}

void dfs(int pos, i128 cur) {
    if (~ans) return;
    if (pos == m - 1) {
        i128 p = 0;
        per(i, m, 0) {
            i128 q = p | i128(1) << i;
            if (q * q <= cur) p = q;
        }
        while (p * p < cur) ++p;
        while (((p * p) >> m) == (cur >> m)) check(p), ++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(cur);
        check(cur | i128(1) << (pos - 1));
        return;
    }
    int tmp = (sqr * sqr) >> pos & 1;
    rep(k, 0, 1) {
        int val = tmp + k * (sqr & 1);
        if (pos == 2) val += k;
        if (match(pos, val & 1)) dfs(pos + 1, cur | i128(val) << pos, sqr | i128(k) << (pos - 1));
    }
}

void solve() {
    cin >> s;
    n = s.size();
    reverse(s.begin(), s.end());
    m = (n + 1) / 2;
    int cnt_left = count(s.begin(), s.end() + m, '?');
    int cnt_right = count(s.begin() + m, s.end(), '?');
    ans = -1;

    if (cnt_left < cnt_right) {
        if (match(0, 0)) dfs(2, 0, 0);
        if (match(0, 1)) dfs(2, 1, 1);
    } else {
        dfs(n - 1, 0);
    }
    per(i, n - 1, 0) cout << int(ans >> i & 1);
    cout << "\n";
}

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

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}