#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 130;

int n, a[maxn], cao;
string str;

void solve1(int m) {
  __int128 L = 0, R = 0;
  rep (i, 1, m) L = L * 2 + a[i], R = R * 2 + a[i];
  rep (i, m + 1, n) L = L * 2, R = R * 2 + 1;
  __int128 l = sqrtl(L), r = sqrtl(R);
  while (l * l < L) L++;
  while (R * R > R) R--;
  for (__int128 x = l; x <= r; x++) {
    __int128 res = x * x;
    int ok = 1;
    rep (i, 1, n) if (a[i] != -1) ok &= (a[i] == (res >> (n - i) & 1));
    if (ok) {
      per (i, n - 1, 0) cout << int(res >> i & 1);
      cao = 1;
      return;
    }
  }
}

bool check(__int128 x, int s, int t, int del) {
  rep (i, s, t) if (a[i] != -1 && a[i] != (x >> (n - i - del) & 1)) return 0;
  return 1;
}

void solve2(int m) {
  int pos = n + 1;
  while (pos - 1 > 0 && a[pos - 1] == 0) pos--;
  pos = max(pos, m + 1);
  if ((n - pos + 1) & 1) return;
  int zero = (n - pos + 1) / 2;
  pos--;
  vector<__int128> vec;
  vec.emplace_back(0);
  int cop = (n - 2 * zero) / 2;
  per (i, pos, max(1, pos - cop)) {
    vector<__int128> nxt;
    for (__int128 x : vec) {
      if (check(x * x, i - 1, i, zero * 2)) nxt.emplace_back(x);
      x |= (((__int128)1) << (pos - i));
      if (check(x * x, i - 1, i, zero * 2)) nxt.emplace_back(x);
    }
    vec = nxt;
  }
  for (__int128 x : vec) {
    x = x * (((__int128)1) << zero);
    __int128 res = x * x;
    if (res >= (((__int128)1) << n)) continue;
    int ok = 1;
    rep (i, 1, n) if (a[i] != -1) ok &= (a[i] == (res >> (n - i) & 1));
    if (ok) {
      per (i, n - 1, 0) cout << int(res >> i & 1);
      cao = 1;
      return;
    }
  }
}

void work() {
  cao = 0;
  cin >> str, n = str.length();
  rep (i, 1, n) {
    if (str[i - 1] == '?') a[i] = -1;
    else a[i] = str[i - 1] - '0';
  }
  int nn = n;
  while (nn >= 4 && a[nn] == a[nn - 1] && a[nn] == 0) nn -= 2;
  int tmp = n - nn;
  n = nn;
  int m = n / 2, c1 = 0, c2 = 0;
  rep (i, 1, m) c1 += (a[i] == -1);
  rep (i, m + 1, n) c2 += (a[i] == -1);
  if (c1 <= c2) {
    vector<int> pos;
    rep (i, 1, m) if (a[i] == -1) pos.emplace_back(i);
    rep (S, 0, (1 << c1) - 1) {
      if (cao) break;
      rep (i, 0, c1 - 1) a[pos[i]] = (S >> i & 1);
      solve1(m);
    }
  } else {
    int pos = n + 1;
    while (pos - 1 > 0 && (a[pos - 1] == -1 || a[pos - 1] == 0)) pos--;
    per (i, n, pos) {
      if (cao) break;
      if (a[i] == -1) a[i] = 1, solve2(m);
      a[i] = 0;
    }
    if (!cao) solve2(m);
  }
  rep (i, 1, tmp) cout << 0;
  cout << '\n';
}

void work2(int dep) {
  cin >> str;
  if (dep == 9) cout << str << endl;
}

int main() {
  // cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  // rep (i, 1, t) cout << "Case #" << i << ": ", work(t);
  rep (i, 1, t) work2(i);
}