#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define rep(i, s, t) for (int i = s; i <= t; ++i)
#define per(i, s, t) for (int i = t; i >= s; --i)

const int N = 135;

int n;
int a[N], b[N];
char str[N];

void solve1() {
	for(int i = 0; i < n; i += 2) {
		if(a[i] != 0) {
			a[i] = 1;
			int m = (i + n) / 2 - i;
			vector<int> v;
			rep(j, i, (i + n) / 2) if(a[j] == -1) v.pb(j);
			int u = (1 << v.size()) - 1;
			rep(s, 0, u) {
				for(int j = 0; j < v.size(); ++j) {
					a[v[j]] = (s >> j & 1);
				}
				unsigned long long x = 0;
				per(j, i, i + 63) x = x << 1 | a[j];
				if((x & 3) == 3) continue;
				unsigned long long y = 1, z = 3;
				int m0 = m + (n % 2);
				for(int j = 2; j < m0; ++j) {
					ull base = ((ull)1 << (j + 2)) - 1;
					auto upd = [&](ull& y) {
						if(((y * y) & base) != (x & base)) {
							y |= (ull)1 << j;
						}
					};
					upd(y);
					upd(z);
				}
				bool flag = 0;
				auto check = [&](unsigned long long y) {
					__int128 r = (__int128)y * (__int128)y;
					bool ok = 1;
					rep(j, i, n-1) if(b[j] != -1) {
						if((r >> (j-i) & 1) != b[j]) ok = 0;
					}
					if(ok) {
						per(i, 0, n-1) cout << (int)(r >> i & 1);
						flag = 1;
						return;
					}
				};
				/*
				for(auto e : st) {
					check(e);
					if(flag) return;
				}
				*/
				check(y);
				if(flag) return;
				check(z);
				if(flag) return;
				check(y | (ull)1 << m);
				if(flag) return;
				check(z | (ull)1 << m);
				if(flag) return;

			}
			for(int j : v) a[j] = -1;
			a[i] = b[i];
		}
		if(a[i] != 1 && a[i+1] != 1) {
			a[i] = a[i+1] = 0;
		} else {
			break;
		}
	}
}

void solve2() {
	vector<int> v;
	for(int i = n / 2; i < n; ++i) if(a[i] == -1) v.pb(i);
	assert(v.size() <= 20);
	int u = (1 << v.size()) - 1;
	__int128 sum = 0;
	per(i, 0, n-1) sum = sum << 1 | (a[i] == 1);
	rep(s, 0, u) {
		__int128 x = sum;
		for(int i = 0; i < v.size(); ++i) {
			a[v[i]] = (s >> i & 1);
			if(a[v[i]]) x |= (__int128)1 << v[i];
		}
		ll r = 0;
		per(i, 0, n/2) {
			ll p = r | 1ll << i;
			if((__int128)p * p <= x) r = p;
		}
		bool flag = 0;
		auto check = [&](__int128 x) {
			bool ok = 1;
			rep(i, 0, n-1) if(b[i] != -1) {
				if((x >> i & 1) != b[i]) {
					ok = 0;
					break;
				}
			}
			if(ok) {
				per(i, 0, n-1) cout << (int)(x >> i & 1);
				flag = 1;
			}
		};
		__int128 res = (__int128)r * r;
		if(res == x) check(res);
		else check((__int128)(r + 1) * (r + 1));
		if(flag) return;
	}
	//assert(0);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cout << fixed << setprecision(15); 
	cerr << fixed << setprecision(15);

	int t; cin >> t;
	rep(cc, 1, t) {
		cout << "Case #" << cc << ": ";
		cin >> str;
		n = strlen(str);
		reverse(str, str + n);
		rep(i, 0, n-1) {
			if(str[i] == '?') a[i] = -1;
			else a[i] = str[i] - '0';
			b[i] = a[i];
		}
		int p = 0;
		while(a[p] == 0) {
			a[p] = a[p+1] = 0;
			p += 2;
		}
		n -= p;
		rep(i, 0, n-1) {
			a[i] = a[i+p];
			b[i] = b[i+p];
			str[i] = str[i+p];
		}
		int c = count(str, str + n, '?');
		if(count(str + n / 2, str + n, '?') <= 20) solve2();
		else solve1();
		rep(i, 1, p) cout << 0; cout << "\n";
	}
	
	return 0;
}