#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=="A")
    {
        if(l[j]==1 or l[j]==2 or l[j]==3)return 1;
        return 0;
    }
    else {
    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;
                    if(solve("A"))return 1;
                    return 0;
                }
                else return 0;
            }
        }
    }
    else
    {
        if(s=="B")
        {
            if(j==n)return 0;
            if(l[j]==2)
            {
                ++j;
                return solve("B");
            }
            else
            {
                if(l[j]==1 && l[j+2]==3 && j+4<=n)
                {
                    j++;
                    if(solve("A"))
                    {
                        j+=2;
                        if(solve("A"))
                        {
                            ++j;
                            return solve("C");
                        }
                        else return 0;
                    }
                    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)fout<<1<<'\n';
            else
            {
                if(n==3 && l[2]==2)
                {
                    j=3;
                    if(solve("A") && j==n)fout<<1<<'\n';
                    else fout<<0<<'\n';
                }
                else{
                if(l[3]==3)
                {
                    j=2;
                    if(solve("A")){
                    j=4;
                    if(solve("A")){
                    ++j;
                    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<<'\n';
                else
                {
                    j=2;
                    if(solve("B") && j==n)fout<<1<<'\n';
                    else fout<<0<<'\n';
                }
            }
            else
            {
                if(l[1]==3){
                if(n==1)fout<<1<<'\n';
                else
                {
                    j=2;
                    zero=solve("B");
                    ++j;
                    if(solve("C") && j==n)fout<<1<<'\n';
                    else fout<<0;
                }
                }
                else fout<<0<<'\n';
            }
        }
    }
    return 0;
}