/**
 * @file qoj5874F1.cpp
 * @author n685
 * @brief
 * @date 2023-07-09
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr                                                                   \
  if (false)                                                                   \
  std::cerr
#endif

using U = __int128_t;
int n;
const __int128_t ONE = 1;
U ans;
U s, a;
bool g = false;

void print(U v) {
  std::string ss;
  for (int i = 0; i < n; ++i) {
    if ((ONE << i) & v)
      ss += "1";
    else
      ss += "0";
  }
  std::reverse(ss.begin(), ss.end());
  cout << ss << '\n';
}

bool good(U val) {
  return (((val * val) & s) == s && ((val * val) | s | a) == (s | a));
}

void solve1() {
  auto gen = [&](auto &self, int node) -> void {
    if (node == n) {
      U v = s | ((ONE << (n >> 1)) - 1);
      U l = 0, r = std::numeric_limits<int64_t>::max();
      while (l < r) {
        U mid = (l + r + 1) / 2;
        if (mid * mid <= v)
          l = mid;
        else
          r = mid - 1;
      }
      if (good(l)) {
        // print(l * l);
        ans = l * l;
        g = true;
      }
      return;
    }
    if (g)
      return;
    self(self, node + 1);
    if (g)
      return;
    if (a & (ONE << node)) {
      s ^= (ONE << node);
      self(self, node + 1);
      s ^= (ONE << node);
    }
  };
  gen(gen, n / 2);
}

void solve2() {
  auto root = [&](U val, bool second) -> U {
    U rt = 1;
    if (second)
      rt ^= 2;
    U v = 0;
    for (int i = 2; i < (n + 1) / 2; ++i) {
      U m = (ONE << (i + 2));
      v = rt;
      v = ((v * v) & (m - 1));
      U res = val & (m - 1);
      if (v != res)
        rt ^= (ONE << i);
    }
    return rt;
  };
  auto gen = [&](auto &self, int node) -> void {
    if (node == (n + 1) / 2 + 2) {
      U rt1 = root(s, false);
      U rt2 = root(s, true);
      if (good(rt1)) {
        ans = rt1 * rt1;
        g = true;
      } else if (good(rt2)) {
        ans = rt2 * rt2;
        g = true;
      }
      return;
    }
    if (g)
      return;
    self(self, node + 1);
    if (g)
      return;
    if ((a & (ONE << node))) {
      s ^= (ONE << node);
      self(self, node + 1);
      s ^= (ONE << node);
    }
  };
  gen(gen, 0);
}

int popcount(U val) {
  int ans = 0;
  while (val > 0) {
    if (val % 2)
      ans++;
    val /= 2;
  }
  return ans;
}

void solve() {
  std::string ss;
  cin >> ss;
  g = false;
  std::reverse(ss.begin(), ss.end());
  n = (int)ss.size();
  int cnt = 0;
  ans = 0;
  s = 0, a = 0;
  for (int i = 0; i < n; ++i) {
    if (ss[i] == '1')
      s ^= (ONE << i);
    else if (ss[i] == '?')
      a ^= (ONE << i);
  }

  while (s % 4 == 0) {
    if (a & 1) {
      s++;
      a--;
    } else {
      a >>= 2;
      s >>= 2;
      cnt += 2;
      n -= 2;
      continue;
    }
    int cnt1 = popcount(a >> (n >> 1));
    int cnt2 = popcount(a & ((ONE << ((n + 1) / 2 + 1)) - 1));

    if (cnt2 < cnt1)
      solve2();
    else
      solve1();
    n += cnt;
    if (g) {
      print(ans << cnt);
      return;
    }

    a >>= 2;
    s >>= 2;
    cnt += 2;
    n -= 2;
  }
  int cnt1 = popcount(a >> (n >> 1));
  int cnt2 = popcount(a & ((ONE << ((n + 1) / 2 + 1)) - 1));

  if (cnt2 < cnt1)
    solve2();
  else
    solve1();
  n += cnt;
  if (g) {
    print(ans << cnt);
    return;
  }
}

int main() {
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

  int t;
  cin >> t;
  for (int tt = 1; tt <= t; ++tt) {
    cout << "Case #" << tt << ": ";
    solve();
  }
}