#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


#ifndef LIBRA_OTHER_INT128_H_
#define LIBRA_OTHER_INT128_H_

#include <stdio.h>
#include <iostream>

constexpr unsigned __int128 toUInt128(const char *s) {
  unsigned __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
constexpr __int128 toInt128(const char *s) {
  if (*s == '-') return -toInt128(s + 1);
  __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
unsigned __int128 inUInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toUInt128(buf);
}
__int128 inInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toInt128(buf);
}

void out(unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) putchar(buf[i]);
}
void out(__int128 x) {
  if (x < 0) {
    putchar('-');
    out(-static_cast<unsigned __int128>(x));
  } else {
    out(static_cast<unsigned __int128>(x));
  }
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) os << buf[i];
  return os;
}
std::ostream &operator<<(std::ostream &os, __int128 x) {
  if (x < 0) {
    os << '-' << -static_cast<unsigned __int128>(x);
  } else {
    os << static_cast<unsigned __int128>(x);
  }
  return os;
}

#endif  // LIBRA_OTHER_INT128_H_


void out2(unsigned __int128 x) {
  static char buf[130];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 2); } while (x /= 2);
  for (int i = len; --i >= 0; ) putchar(buf[i]);
}

using INT = __int128;



inline int half(int E) {
  return (E + 1) / 2;
}

INT solveHi(int E, INT A, INT B) {
// cerr<<"[solveHi] "<<E<<" "<<A<<" "<<B<<endl;
  const INT base = A >> half(E) << half(E);
  const INT mask = (B - A) >> half(E) << half(E);
  for (INT sub = mask; ; --sub &= mask) {
    const INT l = base | sub;
    const INT r = l + ((INT)1 << half(E));
    INT lo = 0, hi = 1LL << half(E);
    for (; lo + 1 < hi; ) {
      const INT mid = (lo + hi) / 2;
      ((mid * mid >= l) ? hi : lo) = mid;
    }
// cerr<<"  ["<<l<<", "<<r<<"): ceil(sqrt(l)) = "<<hi<<endl;
    for (INT x = hi, y; (y = x * x) < r; ++x) {
      if (!(A & ~y) && !(y & ~B)) {
// cerr<<"  found "<<x<<"^2 = "<<y<<endl;
        return x;
      }
    }
    if (!sub) break;
  }
  return 0;
}

// r mod 2^e
INT solveLoDfs(int E, INT A, INT B, int e, INT r) {
// cerr<<"  [solveLoDfs] "<<E<<" "<<A<<" "<<B<<" "<<e<<" "<<r<<endl;
  if (e == half(E)) {
    const INT x = r;
    const INT y = x * x;
    if (!(A & ~y) && !(y & ~B)) {
// cerr<<"  found "<<x<<"^2 = "<<y<<endl;
      return x;
    }
    return 0;
  } else {
    // (r + 2^e s)^2 == r^2 + 2^(e+1) r s  (mod 2^(e+2))  for e >= 2
    if (e == 1 || e == half(E) - 1 || ((B - A) >> (e+1) & 1)) {
      for (INT s = 0; s < 2; ++s) {
        const INT res = solveLoDfs(E, A, B, e + 1, r | s << e);
        if (res) return res;
      }
      return 0;
    } else {
      const INT s = (A ^ (r * r)) >> (e+1) & 1;
      return solveLoDfs(E, A, B, e + 1, r | s << e);
    }
  }
}
INT solveLo(int E, INT A, INT B) {
cerr<<"[solveLo] "<<E<<" "<<A<<" "<<B<<endl;
  return solveLoDfs(E, A, B, 1, 1);
}

INT solve(INT A, INT B) {
  int E = 0;
  for (; !(B < (INT)1 << E); ++E) {}
  const int popHi = __builtin_popcountll((B - A) >> half(E));
  const int popLo = __builtin_popcountll((B - A) & (((INT)1 << half(E)) - 1));
  if (popHi < popLo) {
    return solveHi(E, A, B);
  } else {
    return solveLo(E, A, B);
  }
}

int main() {
  char S[130];
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%s", S);
    const int SLen = strlen(S);
    
    INT A = 0, B = 0;
    for (int e = 0; e < SLen; ++e) {
      if (S[SLen - 1 - e] == '1') A |= (INT)1 << e;
      if (S[SLen - 1 - e] != '0') B |= (INT)1 << e;
    }
    
    INT ans = 0;
    for (int e = 0; B >> (2*e); ++e) {
      const INT res = solve(A >> (2*e), B >> (2*e));
      if (res) {
        ans = res << e;
        break;
      }
    }
cerr<<"ans = "<<ans<<", ans^2 = "<<ans<<endl;
    printf("Case #%d: ", caseId);
    out2(ans * ans);
    puts("");
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}