/**
 * @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 s, a;

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';
}

void solve1() {
  bool g = false;
  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 (((l * l) & s) == s) {
        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() {
  bool g = false;
  auto root = [&](U val, bool second) -> U {
    int cnt = 0;
    while (val % 2 == 0)
      cnt++, val >>= 1;
    if (cnt % 2 == 1)
      return -1;
    U rt = 1;
    if (second)
      rt ^= 2;
    U v = 0;
    for (int i = 2; i < (n + 1) / 2 - cnt / 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 << cnt / 2;
  };
  auto gen = [&](auto &self, int node) -> void {
    if (node == (n + 1) / 2 + 2) {
      U rt1 = root(s, false);
      U rt2 = root(s, true);
      if (((rt1 * rt1) & s) == s) {
        print(rt1 * rt1);
        g = true;
      } else if (((rt2 * rt2) & s) == s) {
        print(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);
}

void solve() {
  std::string ss;
  cin >> ss;
  std::reverse(ss.begin(), ss.end());
  n = (int)ss.size();
  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);
  }
  int cnt1 = __builtin_popcountll((unsigned long long)(a >> (n >> 1)));
  int cnt2 = __builtin_popcountll(
      (unsigned long long)(a & ((ONE << ((n + 1) / 2 + 1)) - 1)));

  // if (cnt2 < cnt1)
  solve2();
  // else
  solve1();
}

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();
  }
}