#include <iostream>
#include <fstream>
#define N 10005
using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

int a[N], n;
int poz;
bool adev;

void functionC();

void functionA()
{
    if(a[poz] == 1 || a[poz] == 2 || a[poz] == 3)
        return;
    else adev = false;
}

void functionB()
{
    if(poz > n)
        adev = false;
    else if(a[poz] == 2)
    {
        poz++;
        functionB();
    }
    else if(a[poz] == 1)
    {
        if((a[poz + 1] == 1 || a[poz + 1] == 2 || a[poz + 1] == 3) && a[poz + 2] == 3 &&
          (a[poz + 3] == 1 || a[poz + 3] == 2 || a[poz + 3] == 3))
                    poz +=4, functionC();
    }
    else
        adev = false;
}

void functionC()
{
    if(poz > n)
        adev = false;
    else if(a[poz] == 2) return;
    else if(a[poz] == 1)
    {
        if(a[poz + 1] == 2 )
            poz += 2, functionA();
        else adev = false;
    }
    else if(a[poz] == 3)
    {
        poz++;
        functionB();
        functionC();

    }
    else adev = false;
}

void solve()
{
    int i;
    poz = 1;

    if(n == 1)
        functionA();
    else
    {
        if(a[1] == 1)
        {
            if(n == 3)
            {
                if(a[2] == 2 && (a[3] == 1 || a[3] == 2 || a[3] == 3))
                    adev = true;
                else adev = false;
            }
            else
            {
                if((a[2] == 1 || a[2] == 2 || a[2] == 3) && a[3] == 3 &&
                   (a[4] == 1 || a[4] == 2 || a[4] == 3))
                   poz += 4, functionC();
            }
        }
        else if(a[1] == 2)
        {
            poz++;
            functionB();
        }
        else
        {
            poz++;
            functionB();
            functionC();
        }

    }
}

void read()
{
    int x, i, j;
    fin >> x;
    for(i = 1; i <= x; ++i)
    {
        fin >> n;
        adev = true;
        for(j = 1; j <= n; ++j)
            fin >>a[j];
        solve();
        if(adev == 1 && poz == n)
            fout << 1 << "\n";
        else
            fout << "0\n";
    }

}



int main()
{
    read();


    return 0;
}


/*A -> 1 | 2 | 3
B -> 2B | 1A3AC
C -> 2 | 3BC | 12A

8 2 1 1 3 2 1 2 3
2 2 2
1 3

321231121

c -> 3BC*/