#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long
using namespace std;
inline LLL solveL(int R,LLL X,LLL Y){
    const LLL Q=(Y-X)>>((R+1)/2)<<((R+1)/2);
    for(LLL S=Q;;(--S)&=Q){
        const LLL l=X|S,r=l+((LLL)1<<((R+1)/2));
        for(LLL Z=sqrtl(l);Z*Z<=r;++Z){
            const LLL Q=Z*Z;
            if((X&Q)==X&&(Y&Q)==Q)return Z;
        }
        if(!S)break;
    }
    return 0;
}
inline LLL solveR(int R,LLL X,LLL Y,int r,LLL Z){
    if(r==R){
        const LLL Q=Z*Z;
        if((X&Q)==X&&(Y&Q)==Q)return Z;
        else return 0;
    }
    if(r==1||r==(R+1)/2-1||((Y-X)>>(r+1)&1)){
        const LLL Q=solveR(R,X,Y,r+1,Z);
        return Q?Q:solveR(R,X,Y,r+1,1<<r|Z);
    }
    return solveR(R,X,Y,r+1,((X^(Z*Z))>>(r+1)&1)<<r|Z);
}
inline LLL solve(LLL X,LLL Y){
    int R=0;for(;((LLL)1<<R)<=X;++R);
    const int cl=__builtin_popcountll((Y-X)>>((R+1)/2));
    const int cr=__builtin_popcountll((Y-X)&(((LLL)1<<((R+1)/2))-1));
    if(cl<cr)return solveL(R,X,Y);else return solveR(R,X,Y,1,1);
}
inline void MAIN(){
    string s;int n;
    cin>>s,n=s.length();
    LLL X=0,Y=0;
    for(int i=0;i<n;++i){
        X*=2,Y*=2;
        if(s[i]=='1')++X;
        if(s[i]!='0')++Y;
    }
    LLL Z=0;
    for(int i=0;Y>>i;i+=2){
        const auto z=solve(X>>i,Y>>i);
        if(z){Z=(z*z)<<i;break;}
    }
    s="";
    while(Z)s.push_back('0'+(Z&1)),Z>>=1;
    reverse(s.begin(),s.end());
    cout<<s<<'\n';
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t=1;cin>>t;for(int i=1;t--;++i)cout<<"Case #"<<i<<": ",MAIN();
    return 0;
}
/*
*/