#include <bits/stdc++.h>

using namespace std;

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

int v[10005],n,t,i,j,ok,nrc=0,k;
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) {
                k=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() {
    in >> t;
    while (t--) {
        in >> n;
        for (i=1; i<=n; i++) {
            in >> v[i];
        }
        ok=0;
        if (n==1) {
            out << 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;
                    }
                }
            }
            out << ok << "\n";
        }
    }
    return 0;
}