#include <fstream>
using namespace std;
int n, poz, i, j, m, v[10001], k;
char st[10001], x;
ifstream fin ("perle.in");
ofstream fout ("perle.out");

int verif()
{
    while (k>0) {
        x=st[k];
        k--;
        if (x=='B') {
            if (v[poz]==2) {
                st[++k]='B';
                poz++;
                if (poz>n-4)
                    return 0;
            }else
                if (v[poz]==1 && v[poz+2]==3) {
                    st[++k]='C';
                    poz+=4;
                    if (poz>n)
                        return 0;
                }
            else
                return 0;
        }else if (x=='C') {
            if(v[poz]==2) {
                poz++;
                if (poz>n && k!=0)
                    return 0;
            }else
                if (v[poz]==3) {
                    st[++k]='C';
                    st[++k]='B';
                    poz++;
                    if (poz>n-4)
                        return 0;
                }
            else
                if (v[poz]==1 && v[poz+1]==2) {
                    poz+=3;
                    if (poz>n && k!=0)
                        return 0;
                }
            else
                return 0;
        }
    }

    if (poz<=n)
        return 0;
    return 1;
}


int main () {
    fin>>m;
    for (i=1;i<=m;i++) {
        fin>>n;
        for (j=1;j<=n;j++)
            fin>>v[j];

        if (n==1) {
            fout<<1<<"\n";
            continue;
        }

        k=1;
        st[k]='B';
        poz=1;
        if (verif()) {
            fout<<1<<"\n";
            continue;
        }

        k=1;
        st[k]='C';
        poz=1;
        fout<<verif()<<"\n";
    }


    return 0;
}