#include<bits/stdc++.h>
using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

const int NMAX=10005;

int t,n,a[NMAX],b[2*NMAX];

inline bool Solve()
{
    int i,j,aux,len=1,kk;
    i=1;
    while (i<=n)
        {
            if (b[i]<=3)
            {
                if (b[i]!=a[i]) return 0;
                else i++;
            }
        else
            {
                if (b[i]==4) {i++;continue;}
                aux=len-i;//cate trebuie mutate
                if (b[i]==5)
                    {
                        if (a[i]==3) return 0;
                        if (a[i]==2) kk=2;
                        if (a[i]==1) kk=5;
                        for (j=len;j>i;j--) b[j+kk-1]=b[j];
                        len+=kk-1;
                        if (kk==2) {b[i]=2;b[i+1]=5;}
                        else
                            {
                                b[i]=1;b[i+1]=4;b[i+2]=3;b[i+3]=4;
                                b[i+4]=6;
                            }
                    }
                else
                    {
                        if (a[i]==2) i++;
                        else
                            {
                                for (j=len;j>i;j--) b[j+3-1]=b[j];
                                len+=2;
                                if (a[i]==3) {b[i]=3;b[i+1]=5;b[i+2]=6;}
                                if (a[i]==1) {b[i]=1;b[i+1]=2;b[i+2]=4;}
                            }
                    }
            }
        }
    if (len==n) return 1;
    return 0;
}

int main()
{
    int i;
    bool ok;
    fin>>t;
    while (t--)
        {
            fin>>n;ok=0;
            for (i=1;i<=n;i++) fin>>a[i];
            //incercam A
            if (n==1) ok=1;
            //incercam B
            b[0]=1;b[1]=5;
            if (Solve()==1) ok=1;
            //incercam C
            b[0]=1;b[1]=6;
            if (Solve()==1) ok=1;

            fout<<ok<<"\n";
        }
    return 0;
}