#include <bits/stdc++.h>
#define MAXL 10000

int v[1 + MAXL];
std::deque <char> dq;
int main(){
    FILE*fi,*fo;
    fi = fopen("perle.in","r");
    fo = fopen("perle.out","w");

    int n;
    fscanf(fi,"%d", &n);
    for(int z = 1; z <= n; z++){
        dq.clear();
        int l;
        fscanf(fi,"%d", &l);
        for(int i = 1; i <= l; i++)
            fscanf(fi,"%d", &v[i]);

        int p;
        if(v[1] == 1){
            if(l == 1){ fprintf(fo,"1\n"); continue;}
            else if(l == 3){
                if(v[2] == 2){ fprintf(fo,"1\n"); continue;}
                else{ fprintf(fo,"0\n"); continue;}
            }
            else if(l < 5){ fprintf(fo,"0\n"); continue;}
            else{
                if(v[3] != 3){ fprintf(fo,"0\n"); continue;}
                else{ p = 5; dq.push_back('C');}
            }
        }
        else if(v[1] == 2){
            if(l == 1){ fprintf(fo,"1\n"); continue;}
            else{ p = 2; dq.push_back('B');}
        }
        else{
            if(l == 1){ fprintf(fo,"1\n"); continue;}
            else{ p = 2; dq.push_back('B'); dq.push_back('C');}
        }

        int ok = 1;
        while(ok && p <= l && !dq.empty()){
            if('1' <= dq.front() && dq.front() <= '3'){
                if(v[p] == dq.front() - '0') p++, dq.pop_front();
                else ok = 0;
            }
            else if(dq.front() == 'A') p++, dq.pop_front();
            else if(dq.front() == 'B'){
                if(v[p] == 1){
                    p++;
                    dq.pop_front();
                    dq.push_front('C');
                    dq.push_front('A');
                    dq.push_front('3');
                    dq.push_front('A');
                }
                else if(v[p] == 2) p++;
                else ok = 0;
            }
            else if(dq.front() == 'C'){
                if(v[p] == 1){
                    p++;
                    dq.pop_front();
                    dq.push_front('A');
                    dq.push_front('2');
                }
                else if(v[p] == 2) p++, dq.pop_front();
                else{
                    p++;
                    dq.pop_front();
                    dq.push_front('C');
                    dq.push_front('B');
                }
            }
        }
        if(!ok || p <= l || !dq.empty()){ fprintf(fo,"0\n"); continue;}
        else{fprintf(fo,"1\n"); continue;}
    }

    return 0;
}