/*
A -> 1 | 2 | 3
B -> 2B | 1A3AC
C -> 2 | 3BC | 12A
321
*/
#include <fstream>
using namespace std;
ifstream cin("perle.in");
ofstream cout("perle.out");
int n,i,j,k,v[10001];
int aux[10001];
bool ok;
void scrie()
{
    for(j=1; j<=aux[0]; j++)
            cout<<aux[j]<<" ";
        cout<<"\n";
}
void muta(int a[],int stop,int nr)
{
    int i;
    a[0]+=nr;
    for(i=a[0]; i>=stop+nr; i--)
        a[i]=a[i-nr];
}
void recurs(int a[], int poz)
{
    int i;
    if(!a[0])
        a[0]++;;
    for(i=poz; i<=a[0]; i++)
    {
        if(a[i]==4)
            a[i]=v[i];
        if(a[i]==5)
        {
            if(v[i]==2)
            {
                muta(a,i,1);
                a[i]=2; a[i+1]=5;
                //scrie();
                recurs(a,i);
            }
            if(v[i]==1)
            {
                muta(a,i,4);
                a[i]=1; a[i+1]=4; a[i+2]=3; a[i+3]=4; a[i+4]=6;
                //scrie();
                recurs(a,i);
            }
            break;
        }
        if(a[i]==6)
        {
            if(v[i]==2)
            {
                //scrie();
                a[i]=2; recurs(a,i);
            }
            if(v[i]==3)
            {
                muta(a,i,2);
                a[i]=3; a[i+1]=5; a[i+2]=6;
                //scrie();
                recurs(a,i);
            }
            if(v[i]==1 && v[i+1]==2)
            {
                muta(a,i,2);
                a[i]=1; a[i+1]=2; a[i+2]=4;
                //scrie();
                recurs(a,i);
            }
           break;
        }
    }
    if(a[0]==k)
        a[0]=a[0];
    if(a[0]==k && a[k]==v[k])
        ok=true;
}
int main()
{
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>k;
        for(j=1; j<=k; j++)
            cin>>v[j];
        //1 2 3 , A=4, B=5, C=6
        ok=false;
        if(k==1)
        {
            aux[1]=4; recurs(aux,1);
        }
        else
        {
            if(v[1]==2 || v[1]==3 || v[1]==1)
            {
                 aux[1]=5; recurs(aux,1);
                 aux[1]=6; recurs(aux,1);
            }
        }
        if(ok==true)
            cout<<"1\n";
        else
            cout<<"0\n";
        for(j=0; j<=k; j++)
            aux[j]=0;
    }
}