#include<bits/stdc++.h>
using namespace std;
typedef __int128 lll;
typedef long long ll;
const lll I = 1;
string str;
int a[130];
int n,m;
bool flag = 0;
void check1(lll x,lll cur)
{
    if(flag) return ;
    int mid = (1+m)/2;
    for(int j = 2;j < mid-1;j++)
    {
        lll X = cur*cur;
        if((X^x) & (I<<(j+1))) cur |= I<<j;
    }
    cur |= I<<(mid-1);
    lll X = cur*cur;
    for(int i = 1;i <= m;i++)
    {
        int b = X>>(i-1)&1;
        if((b^a[i]) == 1) return ;
    }
    for(int i = m;i > 0;i--)
    {
        int b = X>>(i-1)&1;
        cout<<b;
    }
    for(int i = 1;i <= n-m;i++) cout<<0;
    cout<<"\n";
    flag = 1;
    //exit(0);
}
void check2(lll x)
{
    if(flag) return ;
    int mid = (1+m)/2;
    lll cur = ceil(sqrtl(x));
    lll X = cur*cur;
    for(int i = 1;i <= m;i++)
    {
        int b = X>>(i-1)&1;
        if((b^a[i]) == 1) return ;
    }
    for(int i = m;i > 0;i--)
    {
        int b = X>>(i-1)&1;
        cout<<b;
    }
    for(int i = 1;i <= n-m;i++) cout<<0;
    cout<<"\n";flag = 1;
    //exit(0);
}
void sou1(int x,lll y)
{
    if(x == (m+1)/2+1) return check1(y,1),check1(y,3),void();
    if(a[x] != 0 && x != 2) sou1(x+1,y|(I<<(x-1)));
    if(a[x] != 1 && x != 1) sou1(x+1,y);
}
void sou2(int x,lll y)
{
    if(x == m+1) return check2(y),void();
    if(a[x] != 0 && x != 2) sou2(x+1,y|(I<<(x-1)));
    if(a[x] != 1 && x != 1) sou2(x+1,y);
}
void work()
{
    int mid = (m+1)/2,cnt1 = 0,cnt2 = 0;
    for(int i = 1;i <= mid;i++)
        if(a[i] == 2) cnt1++;
    for(int i = mid+1;i <= m;i++)
        if(a[i] == 2) cnt2++;
    //cout<<cnt1<<" "<<cnt2<<"\n";
    //for(int i = 1;i <= m;i++) cout<<a[i]<<" ";
    //cout<<"\n";
    if(cnt1 <= cnt2) sou1(1,0);
    else sou2(mid+1,0);
}
int TT;
int solve()
{
    //system("fc grow1.out grow.out");
    //freopen("grow.in","r",stdin);
    //freopen("grow.out","w",stdout);
    flag = 0;
    ++TT;cin>>str;n = str.size();
    //if(TT < 16) return 0;
    cout<<"Case #"<<TT<<": ";
    for(int i = 1;i <= n;i+=2)
    {
        if(str[n-i] == '0') continue;
        bool Flag = 0;
        for(int j = 1;j < i;j++) if(str[n-j] == '1') Flag = 1;
        if(Flag) continue;
        m = n-i+1;
        for(int j = 1;j <= m;j++)
        {
            if(str[m-j] == '?') a[j] = 2;
            else a[j] = str[m-j]-'0';
        }
        if(m == 2) continue;
        if(m == 1)
        {
            if(flag) continue;
            cout<<1;
            for(int j = 1;j < n;j++) cout<<0;
            cout<<"\n";flag = 1;
            continue;
        }
        work();
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}