#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#ifdef ONLINE_JUDGE
	#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	char buf[1<<21],*p1=buf,*p2=buf;
#endif
#define int long long
using namespace std;typedef __int128 ll;int read(){int num=0,f=1;char c;while(!isdigit(c=getchar()))if(c=='-')f=-1;while(isdigit(c))num=num*10+(c&15),c=getchar();return num*f;}void write(ll x,char ch=' '){int F[40],cnt=0;if(!x)putchar('0');if(x<0)putchar('-'),x=-x;while(x)F[cnt++]=x%10+'0',x/=10;while(cnt)putchar(F[--cnt]);putchar(ch);}
namespace Main
{
    int n;ll L,R,x,y,z,xx,yy,zz,ans;string ch;
    ll cal1(int m,ll l,ll r){const ll S=((r-l)>>((m+1)/2))<<((m+1)/2);for(ll T=S;1;T=(T-1)&S){ll x=l|T,y=x+(((ll)1)<<((m+1)/2));for(ll j=sqrtl(x),t;j*j<=y;++j){t=j*j;if((l&t)==l&&(t&r)==t)return j;}if(!T)break;}return 0;}
    ll cal2(int m,ll l,ll r,int p,ll z){if(p==(m+1)/2){ll t=z*z;if((l&t)==l&&(t&r)==t)return z;return 0;}
    if(p==1||p==(m-1)/2||((r-l)>>(p+1)&1)){ll t=cal2(m,l,r,p+1,z);return t?t:cal2(m,l,r,p+1,z|((ll)1<<p));}
    return cal2(m,l,r,p+1,((l^(z*z))>>(p+1)&1)<<p|z);}
    ll solve(ll l,ll r){int m=0;for(;(((ll)1)<<m)<=l;++m);int c1=__builtin_popcountll((r-l)>>((m+1)/2)),c2=__builtin_popcountll((r-l)&((((ll)1)<<((m+1)/2))-1));
    if(c1<c2)return cal1(m,l,r);return cal2(m,l,r,1,1);}
    void main()
    {
        cin>>ch,L=R=ans=0;for(auto i:ch)L*=2,R*=2,L+=(i=='1'),R+=(i!='0');for(int i=0;R>>i;i+=2){z=solve(L>>i,R>>i);if(z){ans=(z*z)<<i;break;}}ch="";for(;ans;ans>>=1)ch.push_back('0'+(ans&1));reverse(ch.begin(),ch.end()),cout<<ch<<endl;
    }
}
signed main()
{
    const bool base=1,IO=0;int T;if(!base)T=1;else if(IO)T=read();else ios::sync_with_stdio(0),cin>>T;for(int i=1;i<=T;++i){if(base)cout<<"Case #"<<i<<": ";Main::main();}
    return 0;
}