/* name: grow
 * author: 5ab
 * created at: 2024-05-06
 */
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = unsigned long long;
const int N = 125, QC = 40, L = 18;

__int128 stoi128(string s)
{
	__int128 x = 0;
	for (char c : s)
		x = x * 2 + (c - '0');
	return x;
}
string itos128(__int128 x)
{
	return (x >= 2 ? itos128(x / 2) : ""s) + "01"[x % 2];
}

string ans;
bool solve(string s)
{
	int n = ssz(s), m = (n + 1) / 2, sc = 0;
	
	for (int i = 0; i < m; i++)
		sc += s[i] == '?';
	string ss = s;
	auto chk = [&](const string& t) -> bool
	{
		if (ssz(ss) != ssz(t))
			return 0;
		for (int i = 0; i < n; i++)
			if (ss[i] != '?' && ss[i] != t[i])
				return 0;
		return 1;
	};
	if (sc <= L)
	{
		vector<int> qp;
		for (int i = 0; i < m; i++)
			if (s[i] == '?')
				qp.push_back(i);
		for (int i = 0; i < n; i++)
			if (s[i] == '?')
				s[i] = '0';
		int lim = (1 << sc);
		for (int i = 0; i < lim; i++)
		{
			for (int j = 0; j < sc; j++)
				s[qp[j]] = '0' + ((i >> j) & 1);
			auto l = stoi128(s);
			ll al = 0, ar = 1ll << m;
			while (al < ar)
			{
				ll mid = (al + ar) >> 1;
				if (__int128(mid) * mid < l)
					al = mid + 1;
				else
					ar = mid;
			}
			auto rs = __int128(al) * al;
			// assert(__int128(al + 1) * (al + 1) >= l + (1ll << rl));
			// cerr << itos128(rs) << " and\n" << itos128(l) << endl;
			auto ts = itos128(rs);
			if (chk(ts))
			{
				ans = ts;
				return 1;
			}
		}
	}
	else
	{
		assert(s.back() == '1');
		vector<int> qp;
		for (int i = m - 2; i < n; i++)
			if (s[i] == '?')
				qp.push_back(i);
		for (int i = 0; i < n; i++)
			if (s[i] == '?')
				s[i] = '0';
		int lim = (1 << ssz(qp));
		// cerr << ssz(qp) << " " << lim << endl;
		for (int i = 0; i < lim; i++)
		{
			for (int j = 0; j < ssz(qp); j++)
				s[qp[j]] = '0' + ((i >> j) & 1);
			auto l = stoi128(s);
			for (__int128 c : {1, 3})
			{
				// cerr << i << " " << itos128(l) << " " << s << endl;
				for (int j = 2; j < m; j++)
					c |= (((c * c) ^ l) & (1ll << (j + 1))) >> 1;
				auto rs = __int128(c) * c;
				auto ts = itos128(rs);
				// cerr << ts << " " << itos128(c) << endl;
				if (chk(ts))
				{
					ans = ts;
					return 1;
				}
			}
		}
	}
	return 0;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int cas;
	
	cin >> cas;
	for (int cid = 1; cid <= cas; cid++)
	{
		string s, ap;
		
		cin >> s;
		while (!s.empty())
		{
			if (s.back() == '1')
			{
				assert(solve(s));
				break;
			}
			if (s.back() == '?')
			{
				s.back() = '1';
				if (solve(s))
					break;
				s.back() = '0';
			}
			if (end(s)[-2] == '1')
				break;
			s.pop_back();
			s.pop_back();
			ap += "00";
		}
		cout << "Case #" << cid << ": " << ans + ap << endl;
	}
	
	return 0;
}
// started coding at: 05-06 10:05:09

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:7:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::__cxx11::basic_string<char>::_Alloc_hider::~_Alloc_hider()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = char]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/string:54:
/usr/include/c++/13/bits/basic_string.h:181:14: note: called from here
  181 |       struct _Alloc_hider : allocator_type // TODO check __is_final
      |              ^~~~~~~~~~~~