#include <fstream>

using namespace std;

ifstream in("perle.in");
ofstream out("perle.out");
int t, n, ind;
int stop;
int v[10005];

void c();

void b()
{
    if(v[ind] == 2)
    {
        ind++;
        b();

        return;
    }
    else if(ind + 4 <= n && v[ind] == 1 && v[ind + 2] == 3)
    {
        ind += 4;
        c();

        return;
    }
    else
    {
        stop = 1;
        ind = 1e9;
    }
}

void c()
{
    if(v[ind] == 2)
    {
        ind++;

        return;
    }
    else if(v[ind] == 3)
    {
        ind++;
        b();

        if(stop == 1)
        {
            return;
        }

        c();
    }
    else if(ind + 2 <= n && v[ind] == 1 && v[ind + 1] == 2)
    {
        ind += 3;
    }
    else
    {
        stop = 1;
        ind = 1e9;
    }
}

int main()
{
    in>>t;

    while(t--)
    {
        in>>n;
        for(int i = 1; i<=n; i++)
        {
            in>>v[i];
        }

        if(n == 1)
        {
            out<<1<<'\n';
        }
        else
        {
            ind = 1;
            stop = 0;

            b();
            if(ind == n + 1)
            {
                out<<1<<'\n';
            }
            else
            {
                ind = 1;
                stop = 0;

                c();
                if(ind == n + 1)
                {
                    out<<1<<'\n';
                }
                else
                {
                    out<<0<<'\n';
                }
            }
        }
    }
    return 0;
}