#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
int n, z, md, l, r; string s; __int128 msk, nd; bool fnd;
inline void chk(__int128 x)
{
	if ( fnd || ( ( x *= x ) & msk ) != nd ) return;
	Fol(i, n - 1, 0) cout << (int)( ( x >> i ) & 1 ); while ( z-- ) cout << 0; cout << '\n', fnd = true;
}
inline void dfsl(int u, __int128 v, __int128 o)
{
	if ( fnd ) return;
	if ( u == md ) { chk(o), chk(o | ( (__int128)1 << ( u - 1 ) )); return; }
	int nx = ( ( o * o ) >> u ) & 1;
	if ( s[u] == '?' || s[u] == '0' + nx ) dfsl(u + 1, v | ( (__int128)nx << u ), o);
	if ( u != 2 ) nx = !nx;
	if ( s[u] == '?' || s[u] == '0' + nx ) dfsl(u + 1, v | ( (__int128)nx << u ), o | ( (__int128)1 << ( u - 1 ) ));
}
inline void dfsr(int u, __int128 v)
{
	if ( fnd ) return;
	if ( u == md - 1 )
	{
		__int128 o = sqrtl(v);
		while ( o * o < v ) o++;
		while ( ( ( (__int128)o * o ) >> md ) == ( v >> md ) ) chk(o++);
		return;
	}
	if ( s[u] == '?' || s[u] == '0' ) dfsr(u - 1, v);
	if ( s[u] == '?' || s[u] == '1' ) dfsr(u - 1, v | ( (__int128)1 << u ));
}
inline void work()
{
	static int _; cout << "Case #" << ++_ << ": ";
	z = 0, fnd = false, cin >> s, reverse(s.begin(), s.end());
	for ( ; s.size() ; s.erase(0, 2), z += 2 ) if ( s[0] == '?' || s[0] == '1' )
	{
		n = (int)s.size(), s[0] = '1', md = ( n + 1 ) >> 1, msk = nd = 0;
		For(i, 0, n - 1) if ( s[i] != '?' ) msk |= (__int128)1 << i, nd |= (__int128)( s[i] - '0' ) << i;
		if ( count(s.begin(), s.begin() + md, '?') < count(s.begin() + md, s.end(), '?') ) dfsl(2, 1, 1);
		else dfsr(n - 1, 0);
		if ( fnd ) return;
	}
	assert(false);
}
int main()
{
	cin.tie(nullptr) -> sync_with_stdio(false);
	int t; cin >> t; while ( t-- ) work(); return 0;
}