# include <fstream>
# define DIM 40010
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int v[DIM],n,t,i,q,ok;
void potrivireA1();
void potrivireA2();
void potrivireA3();
void potrivireB1();
void potrivireB2();
void potrivireC1();
void potrivireC2();
void potrivireC3();
int main  () {
    fin>>t;
    for(q=1;q<=t;q++){
        fin>>n;
        for(i=1;i<=n;i++)
            fin>>v[i];
        i=0;
        ok=1;
        if(v[1]==1){
            if(n==1)
                potrivireA1();
            else{
                potrivireB1();
                if(i!=n||ok==0){
                    i=0;
                    ok=1;
                    potrivireC1();
                }
            }
        }
        if(v[1]==2){
            if(n==1)
                potrivireA2();
            else
                potrivireB2();
        }
        if(v[1]==3){
            if(n==1)
                potrivireA3();
            else
                potrivireC3();
        }
        if(i==n&&ok)
            fout<<"1\n";
        else
            fout<<"0\n";
    }
    return 0;
}
void potrivireA1(){
    if(ok==0)
        return;
    if((v[++i]!=1)||i>n)
        ok=0;
}
void potrivireA2(){
    if(ok==0)
        return;
    if((v[++i]!=2)||i>n)
        ok=0;
}
void potrivireA3(){
    if(ok==0)
        return;
    if((v[++i]!=3)||i>n)
        ok=0;
}
void potrivireC2(){
    if(ok==0)
        return;
    if((v[++i]!=2)||i>n)
        ok=0;
}
void potrivireB2(){
    if(ok==0)
        return;
    if((v[++i]!=2)||i>n){
        ok=0;
        return;
    }
    if((i+1>n)||v[i+1]==3){
        ok=0;
        return;
    }
    if(v[i+1]==1)
        potrivireB1();
    else
        potrivireB2();
}
void potrivireC1(){
    if(ok==0)
        return;
    if((v[++i]!=1)||i>n){
        ok=0;
        return;
    }
    if((v[++i]!=2)||i>n){
        ok=0;
        return;
    }
    if(i+1>n){
        ok=0;
        return;
    }
    if(v[i+1]==1){
        potrivireA1();
        return;
    }
    if(v[i+1]==2){
        potrivireA2();
        return;
    }
    if(v[i+1]==3){
        potrivireA3();
        return;
    }
}
void potrivireC3(){
    if(ok==0)
        return;
    if((v[++i]!=3)||i>n){
        ok=0;
        return;
    }
    if((i+1>n)||v[i+1]==3){
        ok=0;
        return;
    }
    if(v[i+1]==1)
        potrivireB1();
    else
        potrivireB2();
    if(ok==0)
        return;
    if(i+1>n){
        ok=0;
        return;
    }
    if(v[i+1]==1){
        potrivireC1();
        return;
    }
    if(v[i+1]==2){
        potrivireC2();
        return;
    }
    if(v[i+1]==3){
        potrivireC3();
        return;
    }
}
void potrivireB1(){
    if(ok==0)
        return;
    if((v[++i]!=1)||i>n){
        ok=0;
        return;
    }
    if(i+1>n){
        ok=0;
        return;
    }
    if(v[i+1]==1){
        potrivireA1();
    }else
    if(v[i+1]==2){
        potrivireA2();
    }else
    if(v[i+1]==3){
        potrivireA3();
    }
    if(ok==0)
        return;
    if((v[++i]!=3)||i>n){
        ok=0;
        return;
    }
    if(i+1>n){
        ok=0;
        return;
    }
    if(v[i+1]==1){
        potrivireA1();
    }else
    if(v[i+1]==2){
        potrivireA2();
    }else
    if(v[i+1]==3){
        potrivireA3();
    }
    if(ok==0)
        return;
    if(i+1>n){
        ok=0;
        return;
    }
    if(v[i+1]==1){
        potrivireC1();
        return;
    }
    if(v[i+1]==2){
        potrivireC2();
        return;
    }
    if(v[i+1]==3){
        potrivireC3();
        return;
    }
}