#include <cstdio>
#include <stack>

using namespace std;

stack <int> stiva;
int n,v[10001];
const int a=4,b=5,c=6;
int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    int t,i;
    scanf("%d",&t);
    for(t;t;--t)
    {
        for(i=1;i<=n;++i)
            v[i]=0;
        while(!stiva.empty())stiva.pop();
        scanf("%d",&n);
        for(i=1;i<=n;++i)
            scanf("%d",v+i);
        if(n==1)
            {printf("1\n");continue;}
        if(n==2)
            {printf("0\n");continue;}
        if(n==3)
        {
            if(v[1]==1 and v[2]==2)
                printf("1\n");
            else
                printf("0\n");
            continue;
        }
        if(v[1]==1)
            stiva.push(c),stiva.push(a),stiva.push(3),stiva.push(a);
        if(v[1]==2)
            stiva.push(b);
        if(v[1]==3)
            stiva.push(c),stiva.push(b);
        int ok=1;
        for(i=2;i<=n;++i)
        {
            if(stiva.top()<=3)
                if(stiva.top()==v[i])
                    {stiva.pop();continue;}
                else
                    {ok=0;break;}
            if(stiva.top()==a)
                {stiva.pop();continue;}
            if(stiva.top()==b)
            {
                if(v[i]==3)
                    {ok=0;break;}
                if(v[i]==1)
                    stiva.pop(),stiva.push(c),stiva.push(a),stiva.push(3),stiva.push(a);
                continue;
            }
            if(stiva.top()==c)
            {
                if(v[i]==3)
                    stiva.pop(),stiva.push(c),stiva.push(b);
                if(v[i]==2)
                    stiva.pop();
                if(v[i]==1)
                    stiva.pop(),stiva.push(a),stiva.push(2);
                continue;
            }
        }
        if(ok==0 or !stiva.empty())
            printf("0\n");
        else
            printf("1\n");
    }
    return 0;
}