#include<iostream>
#include<cstdio>
#include<fstream>

using namespace std;
ofstream g("perle.out");

char s[20];
int l, v[100];

void ver(int m)
{
    if(v[m]==1)
    {
        if(m>3) if((v[m-3]==1)&&(v[m-1]==3)){ s[m-3]='b'; if(m>4) ver(m-4); m=m-3;}
        else if(m>2) if((v[m-1]==2)&&(v[m-2]==1)){ s[m-2]='c'; if(m>3) ver(m-3); m=m-2;}
    }
    else if(v[m]==2)
    {
        if (m<l)
        {
            if (m>3) if((v[m-1]==3)&&(v[m-3]==1)&&((s[m+1]=='c')||(v[m+1]==2))){ s[m-3]='b'; if(m>4) ver(m-4); m=m-3;}
            else if(s[m+1]=='b'){ s[m]='b'; if(m>1) ver(m-1);}
        }
        else if (m>4) if((v[m-2]==3)&&(v[m-4]==1)){ s[m-4]='b'; if(m>5) ver(m-5); m=m-4;}
        else if (m>2) if((v[m-1]==2)&&(v[m-2]==1)){ s[m-2]='c';  if(m>3) ver(m-3); m=m-2;}
    }
    else if(v[m]==3)
    {
        if (m<l-1) if((s[m+1]=='b')&&(s[m+2]=='c')){ s[m]='c'; if(m>1) ver(m-1);}
        else if ((m>3)&&(m<l)) if((v[m-1]==3)&&(v[m-3]==1)&&(s[m+1]=='c')){ s[m-3]='b'; if(m>4) ver(m-4); m=m-3;}
        else if (m>2) if((v[m-1]==2)&&(v[m-2]==1)){ s[m-2]='c'; if(m>3) ver(m-3); m=m-2;}
    }
    if(m==1)
    {
        if(s[m]=='b') g<<"1"<<"\n";
        else if(s[m]=='c') g<<"1"<<"\n";
        else g<<"0"<<"\n";
    }
    else g<<"0"<<"\n";
}

int main()
{
    int n, i, j;
    //char s[20];
    freopen("perle.in", "r", stdin);
    ifstream f("perle.in");
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>l;
        for(j=1; j<=l; j++)
        {
            f>>v[j];
            cout<<v[j]<<' ';
            s[j]='d';
        }
        cout<<"\n";
        if(l==1) g<<"1"<<"\n";
        else if(l==2) g<<"0"<<"\n";
        else ver(l);

    }
}