#include <fstream>
#include <iostream>
using namespace std;

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

int a(),b(),c();
int n,m,i,j,cnt,v[10001];

int a(){
    if(i==n+1){
        return 0;
    }

    if(v[i]==1 || v[i]==2 || v[i]==3){
        i++;
        return 1;
    }else{
        return 0;
    }
}

int b(){
    if(i==n+1){
        return 0;
    }

    if(v[i]==2){
        i++;
        return b();
    }

    if(v[i]==1){
        i++;

        if(!a()){
            return 0;
        }

        if(v[i]!=3){
            return 0;
        }
        i++;

        if(!a()){
            return 0;
        }

        if(!c()){
            return 0;
        }

        return 1;
    }
}

int c(){
    if(i==n+1){
        return 0;
    }

    if(v[i]==2){
        i++;
        return 1;
    }

    if(v[i]==3){
        i++;

        if(!b())
            return 0;

        if(!c())
            return 0;

        return 1;
    }

    if(v[i]==1 && v[i+1]==2)
        i+=2;
    else
        return 0;

    if(!a())
        return 0;

    return 1;
}

int main(){
    for(fin>>m;m;m--){
        for(i=1;i<=n;i++)
            v[i]=0;
        fin>>n;
        for(i=1;i<=n;i++)
            fin>>v[i];

        i=1; j=a();
        if(j==1 && i==n+1){
            fout<<"1\n";
            continue;
        }

        i=1; j=b();
        if(j==1 && i==n+1){
            fout<<"1\n";
            continue;
        }

        i=1; j=c();
        if(j==1 && i==n+1){
            fout<<"1\n";
            continue;
        }

        fout<<"0\n";
    }

    return 0;
}