#include <cstdio>
#include <algorithm>
#define lmax 10005
using namespace std;
FILE *f=fopen("perle.in","r");
FILE *g=fopen("perle.out","w");
int l,v[lmax*2],s[lmax*2],nr;
bool ok=false;

void bkt(int num)
{int i;
if (num>l) {if (nr==l) ok=true;
            return;}
if (v[num]==s[num]||s[num]==-1) {s[num]=v[num];
                                  bkt(num+1);
                                  return;}
if (s[num]==-2) {if (v[num]==2) {for (i=nr+1;i>num+1;i--)
                                            {s[i]=s[i-1];
                                             s[i-1]=0;}
                                 nr++;
                                  s[num]=v[num];
                                 s[num+1]=-2;
                                 bkt(num+1);
                                 }else
                 if (v[num]==1) {for (i=nr+4;i>num+4;i--)
                                            {s[i]=s[i-4];
                                             s[i-4]=0;
                                            }
                                 nr+=4;
                                 s[num]=v[num];
                                 s[num+1]=-1;
                                 s[num+2]=3;
                                 s[num+3]=-1;
                                 s[num+4]=-3;
                                 bkt(num+1);
                                 }
                 }
if (s[num]==-3) {if (v[num]==2) {s[num]=v[num];
                                 bkt(num+1);
                                 }else
                 if (v[num]==3) {for (i=nr+3;i>num+2;i--)
                                            {s[i]=s[i-2];
                                             s[i-2]=0;
                                             }
                                 nr+=2;
                                 s[num]=v[num];
                                 s[num+1]=-2;
                                 s[num+2]=-3;
                                 bkt(num+1);
                                 }else
                 if (v[num]==1) {for (i=nr+3;i>num+2;i--)
                                            {s[i]=s[i-2];
                                             s[i-2]=0;
                                             }
                                 nr+=2;
                                 s[num]=v[num];
                                 s[num+1]=2;
                                 s[num+2]=-1;
                                 bkt(num+1);
                                 }
                 }


}


void rez()
{int i;
ok=false;
for (i=1;i<=3;i++) if (ok==false)
        {fill(s,s+nr+2,0);
         nr=1;
         s[nr]=-i;
         bkt(1);}
if (ok==true) fprintf(g,"%d\n",1);
         else fprintf(g,"%d\n",0);
}


int main()
{int n;
fscanf(f,"%d",&n);
while (n!=0)
    {--n;
     fscanf(f,"%d",&l);
     for (int i=1;i<=l;i++) fscanf(f,"%d",&v[i]);
     rez();
     fill(v,v+l+1,0);
     }

return 0;
}