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