//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int tc=1;tc<=t;tc++)
	{
		string s;
		cin>>s;
		int m=sz(s);
		int cnt0=0,cnt1=0;
		for(int i=0;i<m;i++)
			if(s[i]=='?')
			{
				if(i<m/2)
					cnt0++;
				else
					cnt1++;
			}
		if(cnt0<=cnt1)
		{
			bool flag=0;
			for(int i=0;i<(1<<cnt0)&&!flag;i++)
			{
				longer mnval=0,mxval=0;
				int c=0;
				for(int j=0;j<m;j++)
				{
					mnval<<=1;
					mxval<<=1;
					if(s[j]!='?')
					{
						mnval|=(s[j]&1);
						mxval|=(s[j]&1);
					}
					else if(c<cnt0)
					{
						mnval|=(i>>c&1);
						mxval|=(i>>c&1);
						c++;
					}
					else
						mxval|=1;
				}
				longer a=sqrt((long double)mnval),b=sqrt((long double)mxval);
				for(longer x=a;x<=b&&!flag;x++)
				{
					longer val=x*x;
					if((val&mnval)==mnval)
					{
						longer diff=mnval^val;
						longer tmp=mnval^mxval;
						if((diff&tmp)==diff)
						{
							flag=1;
							cout<<"Case #"<<tc<<": ";
							for(int i=m-1;i>=0;i--)
								cout<<(int)(val>>i&1);
							cout<<'\n';
						}
					}
				}
			}
		}
		else
		{
			bool flag=0;
			for(int i=0;i<(1<<cnt1)&&!flag;i++)
			{
				longer mnval=0,mxval=0;
				int c=0;
				for(int j=0;j<m;j++)
				{
					mnval<<=1;
					mxval<<=1;
					if(s[j]!='?')
					{
						mnval|=(s[j]&1);
						mxval|=(s[j]&1);
					}
					else if(j>=m/2)
					{
						mnval|=(i>>c&1);
						mxval|=(i>>c&1);
						c++;
					}
					else
						mxval|=1;
				}
				longer x=0;
				bool ok=1;
				for(int j=m-1;j>=m/2;j++)
				{
					bool fl=0;
					for(int k=0;k<2;k++)
					{
						longer tmp=x|((longer)(k)<<(m-j-1));
						longer target=mnval&(((longer)(1)<<(m-j))-1);
						if((tmp*tmp)&(((longer)(1)<<(m-j))-1)==target)
						{
							fl=1;
							x=tmp;
							break;
						}
					}
					if(!fl)
					{
						ok=0;
						break;
					}
				}
				if(!ok)
					continue;
				for(int i=0;i<8&&!flag;i++)
				{
					longer cur=x+((longer)(i)<<(m-(m/2)));
					longer val=cur*cur;
					if((val&mnval)==mnval)
					{
						longer diff=mnval^val;
						longer tmp=mnval^mxval;
						if((diff&tmp)==diff)
						{
							flag=1;
							cout<<"Case #"<<tc<<": ";
							for(int i=m-1;i>=0;i--)
								cout<<(int)(val>>i&1);
							cout<<'\n';
						}
					}
				}
			}
		}
	}
	return 0;
}