#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
//#include <windows.h>
//#include<stdio.h>
//#include<time.h>
int arr[10000], art[10000];
bool raspuns =  false;
int cate_pe_rand;
// -1 - A, 4-B, 5-C
int work(int p, char rule) // int pt ca returnez cate pozitii in fata am putut merge cu recursivitatea
//                          p este defapt pozitia
{
    // clauza de final de vector, adica raspuns = true
//    if(arr [p + 1] == -2)
//    {
//        raspuns = true;
//    }
    if(rule == 'b' and !raspuns)
    {
        if(arr[p] == 2)
        {
            int pozitie;
            pozitie = work(p + 1, 'b');
            if(pozitie == cate_pe_rand - 1 and arr[pozitie + 1] == -2) raspuns = true;
            return pozitie;
        }
        if(arr[p] == 1)
        {
            int pozitie;
            pozitie = work(p + 4, 'c');
            if(pozitie == cate_pe_rand - 1 and arr[pozitie + 1] == -2) raspuns = true;
            if(arr[p + 2] != 3)raspuns = false;
            return pozitie;
        }
    }
    if(rule == 'c' and !raspuns)
    {
        if(arr[p] == 3)
        {
            int pozitie, pozitie2;
            pozitie = work(p+1, 'b');
            if(pozitie == cate_pe_rand - 1 and arr[pozitie + 1] == -2) raspuns = true;
            pozitie2 = work(pozitie +1, 'c');
            if(pozitie2 == cate_pe_rand - 1 and arr[pozitie2 + 1] == -2) raspuns = true;
            return pozitie2;
        }
        if(arr[p] == 1 and arr[p + 1] == 2)
        {
//            art[p + 3] = -1;
            return p + 2;
        }
        if(arr[p] == 2)
        {
            return p;
        }
    }
    return p + 1;
}

int main()
{
//    srand(time(NULL));
//    for ( int as = 0; as < 20; ++as)
//    {
//        int a = rand() % 20;
//        for(int i = 0; i < a; ++i)cout << rand() % 3 + 1 ;
//        cout << endl;
//    }
    int cate_teste;
    fin >>cate_teste;
//    memset(arr, '-2', 10000);
    for(int dispearsable = 0; dispearsable < 10000; ++ dispearsable) arr[dispearsable] = -2;
    for( int var = 0; var < cate_teste; ++ var)
    {
        fin >> cate_pe_rand;
        for(int inutil = 0; inutil < cate_pe_rand; ++ inutil)
        {
            fin >> arr[inutil];
        }
        work(0, 'b');
        work(0, 'c');
        if(cate_pe_rand == 1) raspuns = true;
        fout << raspuns << '\n' ;
        raspuns = false;
            for(int dispearsable = 0; dispearsable < cate_pe_rand; ++ dispearsable) arr[dispearsable] = -2;

    }

    return 0;
}
////////////////////*
////////////////////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;
//    }
//}