main secrert

#include<bits/stdc++.h>
using namespace std;
string d2b(int n)
{
    string s;
    while(n)
    {
        s+=n%2+'0';
        n/=2;
    }
    //reverse (s.begin(),s.end());
    return s;

}
int main(){
    int tc,n;
    scanf("%d",&tc);
    for(int i=1; i<=tc; i++){
        scanf("%d",&n);
        string s;
        s=d2b(n);
        string ans=s;
        reverse(ans.begin(),ans.end());

        cout<<ans<<endl;
        int l=s.size();
        int f=0,ct=0;

        if(s[0]=='0'){
            for( int i=0; i<l; i++){
                ct++;
                f=3;
                if(s[i]=='1') break;
            }
            int a=0;
        for(int i=l-ct; ; i++){
                a++;

            s[i]='0';
            if(a==ct) break;


        }
       // s+='1';
        }

        if(f==0)
            for(int i=0; i<l; i++){
                if(s[i]=='0'){
                    swap(s[i],s[i-1]);
                    f=1;
                    break;
                }

            }

        if(f==0){
            s[l-1]='0';
            s+='1';

        }
        cout<<f<<endl;

        reverse(s.begin(),s.end());
        cout<<s<<endl;

    }
    return 0;
}