#include <fstream>
#include <stack>
#define A 4
#define B 5
#define C 6
using namespace std;
ifstream fin ("perle.in");
ofstream fout ("perle.out");
int n, t, v[10005], s[5*10005], vf;
int este_ok()
{
    int cur=1;
    while(cur<=n and vf>0)
    {
        if(v[cur]==s[vf] or s[vf]==A)
        {
            cur++;
            vf--;
            continue;
        }
        if(s[vf] < A)
            return 0;
        if(s[vf]==B)
        {
            if(v[cur]==1)
            {
                s[vf++]=C;
                s[vf++]=A;
                s[vf++]=3;
                s[vf]=A;
                cur++;
                continue;
            }
            if(v[cur]==2)
            {
                cur++;
                continue;
            }
            if(v[cur]==3)
                return 0;
        }
        if(s[vf]==C)
        {
            if(v[cur]==1)
            {
                s[vf++]=A;
                s[vf]=2;
                cur++;
                continue;
            }
            if(v[cur]==2)
            {
                cur++;
                vf--;
                continue;
            }
            if(v[cur]==3)
            {
                s[vf++]=C;
                s[vf]=B;
                cur++;
                continue;
            }
        }
    }
    if(cur==n+1 and vf==0)
        return 1;
    return 0;
}
int main()
{
    fin>>t;
    for(int ti=1; ti<=t; ti++)
    {
        fin>>n;
        for(int i=1;i<=n;i++)
        {
            fin>>v[i];

        }
        int ok=0;
        for(int i=A; i<=C; i++)
        {
            vf=1;
            s[vf]=i;
            if(este_ok())
                ok=1;
        }
        fout<<ok<<'\n';
    }
    return 0;
}