#include <fstream>
#include <deque>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
int t,n,i,v[10001],p;
char c;
deque<char>dq;
int main() {
    f>>t;
    while(t>0) {
        t--;
        f>>n;
        for(i=1; i<=n; i++) {
            f>>v[i];
        }
        if(n==1) {
            g<<1<<'\n';
        } else {
            p=1;
            dq.push_front('B');
            while(!dq.empty()) {
                c=dq.front();
                dq.pop_front();
                if(c=='A') {
                    p++;
                } else if(c=='B' && v[p]==2) {
                    dq.push_front('B');
                    p++;
                } else if(c=='B' && v[p]==1 && v[p+2]==3) {
                    p+=4;
                    dq.push_front('C');
                } else if(c=='C' && v[p]==2) {
                    p++;
                } else if(c=='C' && v[p]==3) {
                    p++;
                    dq.push_front('C');
                    dq.push_front('B');
                } else if(c=='C' && v[p]==1 && v[p+1]==2) {
                    p+=3;
                } else {
                    p=n+2;
                    break;
                }
            }
            while(!dq.empty()) {
                dq.pop_back();
            }
            if(p==n+1) {
                g<<1<<'\n';
            } else {
                p=1;
                dq.push_front('C');
                while(!dq.empty()) {
                    c=dq.front();
                    dq.pop_front();
                    if(c=='A') {
                        p++;
                    } else if(c=='B' && v[p]==2) {
                        dq.push_front('B');
                        p++;
                    } else if(c=='B' && v[p]==1 && v[p+2]==3) {
                        p+=4;
                        dq.push_front('C');
                    } else if(c=='C' && v[p]==2) {
                        p++;
                    } else if(c=='C' && v[p]==3) {
                        p++;
                        dq.push_front('C');
                        dq.push_front('B');
                    } else if(c=='C' && v[p]==1 && v[p+1]==2) {
                        p+=3;
                    } else {
                        p=n+2;
                    }
                }
                while(!dq.empty()) {
                    dq.pop_back();
                }
                if(p==n+1) {
                    g<<1<<'\n';
                } else {
                    g<<0<<'\n';
                }
            }
        }
    }
    return 0;
}