#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int p[1001000];
bool ok[4];
bool sth[4][1001000];
int ans[1001000];
int n;

void manacher(int x)
{
    for(int i=0; i<n; i++)
    {
        ans[i]=0;
    }
    int lo=0,hi=0;
    for(int i=1; i<n-1; i++)
    {
        ans[i]=min(hi-i,ans[hi-i+lo]);
        // if(x==0)
        //     cout<<i<<" "<<ans[i]<<" "<<sth[x][i-ans[i]-1]<<" "<<sth[x][i+ans[i]+1]<<"\n";
        while(i-ans[i]-1>=0 && i+ans[i]+1<n && sth[x][i-ans[i]-1] == sth[x][i+ans[i]+1])
            ++ans[i];
        if(i+ans[i]>i)
        {
            lo=i-ans[i];
            hi=i+ans[i];
        }
    }
}

int main()
{
    // cin.tie(0);
    // ios_base::sync_with_stdio(0);
    int tst;
    cin>>tst;
    while(tst--)
    {
        cin>>n;
        for(int i=0; i<n; i++)
            cin>>p[i];
        sth[0][0]=0;
        sth[0][1]=0;
        for(int i=2; i<n; i+=2)
        {
            if(p[i-1]!=0)
                sth[0][i]=sth[0][i-2];
            else
                sth[0][i]=!sth[0][i-2];
        }
        for(int i=3; i<n; i+=2)
        {
            if(p[i-1]!=0)
                sth[0][i]=sth[0][i-2];
            else
                sth[0][i]=!sth[0][i-2];
        }
        // for(int i=0; i<n; i++)
        //     cout<<sth[0][i];
        // cout<<"\n";
        manacher(0);
        ok[0]=1;
        for(int i=0; i<n; i++)
        {
            // cout<<p[i]<<" "<<ans[i]<<"\n";
            if(p[i]!=ans[i])
            {
                ok[0]=0;
                break;
            }
        }
        // cout<<"WTHHESWT???\n";
        

        sth[1][0]=0;
        sth[1][1]=1;
        for(int i=2; i<n; i+=2)
        {
            if(p[i-1]!=0)
                sth[1][i]=sth[1][i-2];
            else
                sth[1][i]=!sth[1][i-2];
        }
        for(int i=3; i<n; i+=2)
        {
            if(p[i-1]!=0)
                sth[1][i]=sth[1][i-2];
            else
                sth[1][i]=!sth[1][i-2];
        }
        manacher(1);
        ok[1]=1;
        for(int i=1; i<n; i++)
            if(p[i]!=ans[i])
            {
                ok[1]=0;
                break;
            }
        
        
        sth[2][0]=1;
        sth[2][1]=0;
        for(int i=2; i<n; i+=2)
        {
            if(p[i-1]!=0)
                sth[2][i]=sth[2][i-2];
            else
                sth[2][i]=!sth[2][i-2];
        }
        for(int i=3; i<n; i+=2)
        {
            if(p[i-1]!=0)
                sth[2][i]=sth[2][i-2];
            else
                sth[2][i]=!sth[2][i-2];
        }
        manacher(2);
        ok[2]=1;
        for(int i=0; i<n; i++)
            if(p[i]!=ans[i])
            {
                ok[2]=0;
                break;
            }


        sth[3][0]=1;
        sth[3][1]=1;
        for(int i=2; i<n; i+=2)
        {
            if(p[i-1]!=0)
                sth[3][i]=sth[3][i-2];
            else
                sth[3][i]=!sth[3][i-2];
        }
        for(int i=3; i<n; i+=2)
        {
            if(p[i-1]!=0)
                sth[3][i]=sth[3][i-2];
            else
                sth[3][i]=!sth[3][i-2];
        }
        manacher(3);
        ok[3]=1;
        for(int i=0; i<n; i++)
            if(p[i]!=ans[i])
            {
                ok[3]=0;
                break;
            }

        int res=0;
        for(int i=0;i<4; i++)
            if(ok[i])
                res++;
        cout<<res<<"\n";
        for(int i=0; i<4; i++)
        {
            if(ok[i])
            {
                for(int j=0; j<n; j++)
                    cout<<sth[i][j];
                cout<<"\n";
            }
        }
    }
}