#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
const int Nmax=10000+5;
int l[Nmax];
bool zero;
int n,t,j=0;
int solve(string s)
{
    if(s=="C")
    {
        if(l[j]==2)return 1;
        else
        {
            if(l[j]==3)
            {
                j++;
                zero=solve("B");
                ++j;
                return solve("C");
            }
            else
            {
                if(l[j]==1 && l[j+1]==2)
                {
                    j+=2;
                    return 1;
                }
                else return 0;
            }
        }
    }
    else
    {
        if(s=="B")
        {
            if(j==n)return 0;
            if(l[j]==2)
            {
                ++j;
                solve("B");
            }
            else
            {
                if(l[j]==1 && l[j+2]==3 && j+4<=n)
                {
                    j += 4;
                    solve("C");
                }
                else return 0;
            }
        }
    }
}
int main()
{
    fin>>t;
    while(t--)
    {
        fin>>n;
        for(int i=1;i<=n;++i)fin>>l[i];
        if(l[1]==1)
        {
            if((n==1 or n==2) || (l[2]==2 && n==3))fout<<1<<'\n';
            else
            {
                if(l[3]==3)
                {
                    j=5;
                    if(solve("C") && j==n)fout<<1<<'\n';
                    else fout<<0<<'\n';
                }
                else fout<<0<<'\n';
            }
        }
        else
        {
            if(l[1]==2)
            {
                if(n==1)fout<<1;
                else
                {
                    j=2;
                    if(solve("B") && j==n)fout<<1<<'\n';
                    else fout<<0<<'\n';
                }
            }
            else
            {
                if(n==1)fout<<1<<'\n';
                else
                {
                    j=2;
                    zero=solve("B");
                    ++j;
                    if(solve("C") && j==n)fout<<1<<'\n';
                    else fout<<0;
                }
            }
        }
    }
    return 0;
}