#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int v[10005], n, t, i, j, ok, nrc=0;
char sir[10005], ch[5];
int funct(char ch) {
    if(i>n) {
        ok=0;
        return 1;
    }
    if(ch=='B') {
        if(v[i]==2) {
            i++;
            funct('B');
        } else if(v[i]==1 && v[i+2]==3 && i<=n-4) {
            i+=4;
            funct('C');
        }
    } else {
        if(v[i]==2) {
            if(i==n) ok=1;
            else {
                i++;
                return 1;
            }
        } else if(v[i]==1 && v[i+1]==2) {
            if(i+2==n) ok=1;
            else {
                i+=3;
                return 1;
            }
        } else if(v[i]==3) {
            i++;
            funct('B');
            funct('C');
        }
    }
}
int main() {
    fin >> t;
    for(j=1; j<=t; j++) {
        fin >> n;
        for(i=1; i<=n; i++)
            fin >> v[i];
        ok=0;
        if(n==1)   fout << 1 << "\n";
        else {
            if(v[1]==2) {
                i=2;
                funct('B');
            } else if(v[1]==3) {
                i=2;
                funct('B');
                funct('C');
            } else {
                if(v[1]==1 && v[3]==3) {
                    i=5;
                    funct('C');
                }
                if(v[1]==1 && v[2]==2 && n==3)   ok=1;
            }
            fout << ok << "\n";
        }
    }


    return 0;
}