#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){
        ///cout<<"a";
        return 0;
    }

    if(v[i]==1 || v[i]==2 || v[i]==3){
        i++;
        return 1;
    }else{
        ///cout<<"a";
        return 0;
    }
}

int b(){
    cnt++;
    if(i==n+1){
        ///cout<<"b"<<" "<<i;
        return 0;
    }

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

            if(!a()){
                ///cout<<"b"<<cnt;
                return 0;
            }

            if(v[i]!=3){
                ///cout<<"b"<<cnt;
                return 0;
            }
            i++;

            if(!a()){
                ///cout<<"b"<<cnt;
                return 0;
            }

            if(!c()){
                ///cout<<"b"<<cnt;
                return 0;
            }

            return 1;
        }else
            return 0;
    }
}

int c(){
    if(i==n+1){
        ///cout<<"c";
        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)
        ///cout<<i<<" ",i+=2;

    int x=a();
    ///cout<<x;

    if(!x)
        return 0;

    return 1;
}

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

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

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

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

        fout<<"0\n";
    }

    return 0;
}