#include <fstream>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <vector>
#define Nmax 1201
using namespace std;

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

int q, n;
int V[10001], N[10001];

void A(int &pos);
void B(int &pos);
void C(int &pos);

void A(int &pos){
    if(V[pos] == 0)
        pos = 9999;
    N[pos] = V[pos];
    pos++;
}
void B(int &pos){
    if(V[pos] == 0)
        pos = 9999;

    if(V[pos] == 2){
        N[pos] = 2;
        B(++pos);
    }
    else if(V[pos] == 1 && V[pos + 2] == 3){
        N[pos++] = 1;
        A(pos);
        N[pos++] = 3;
        A(pos);
        C(pos);
    }

}
void C(int &pos){
    if(V[pos] == 0)
        pos = 9999;

    if(V[pos] == 2){
        N[pos] = 2;
    }
    else if(V[pos] == 3){
        N[pos++] = 3;
        B(pos);
        pos++;
        C(pos);
        pos++;
    }
    else if(V[pos] == 1 && V[pos + 1] == 2){
        N[pos++] = 1;
        N[pos++] = 2;
        A(pos);
    }
}

int main(){
    fin >> q;

    while(q--){
        fin >> n;

        for(int i = 1; i <= n; ++i){
            fin >> V[i];
        }

        for(int i = n + 1; i <= n + 5; ++i)
            V[i] = 0;

        int pos = 1;
        
        bool ok = 0;

        if(n == 1)
            fout << 1 << "\n";
        else
            if(V[1] == 1){
                C(pos);

                bool verif = 1;

                if(pos - 1 > n)
                    verif = 0;
                
                for(int j = 1; j <= n; ++j)
                    if(N[j] != V[j])
                        verif = 0;
                
                if(verif)
                    ok = 1;
                
                pos = 1;

                B(pos);

                if(pos - 1 > n)
                    verif = 0;
                
                for(int j = 1; j <= n; ++j)
                    if(N[j] != V[j])
                        verif = 0;
                
                if(verif)
                    ok = 1;
            }
            else
                if(V[1] == 2){
                    bool verif = 1;

                    pos = 1;

                    B(pos);

                    if(pos - 1 > n)
                        verif = 0;
                    
                    for(int j = 1; j <= n; ++j)
                        if(N[j] != V[j])
                            verif = 0;
                    
                    if(verif)
                        ok = 1;
                }
                else{
                    bool verif = 1;

                    pos = 1;

                    C(pos);

                    if(pos - 1 > n)
                        verif = 0;
                    
                    for(int j = 1; j <= n; ++j)
                        if(N[j] != V[j])
                            verif = 0;
                    
                    if(verif)
                        ok = 1;
                }
        if(n != 1)
        fout << ok <<"\n";
    }
}