#include <fstream>
#define nmax 10100
using namespace std;

int N,V[nmax];

int C(int);

bool A(int i) {
    return N==1;
}
int B(int i) {

    if(i>N)
        return 0;
    else
    if(V[i]==2)
        return B(i+1);
    else
    if(i+2<=N&&V[i]==1&&V[i+2]==3);
        return C(i+4);

    return 0;

}
int C(int i) {

    if(i>N)
        return 0;
    else
    if(V[i]==2)
        return i;
    else
    if(i+1<=N&&V[i]==1&&V[i+1]==2)
        return i+2;
    else {
        int k=B(i+1);
        if(k)
            return C(k+1);
        }

    return 0;

}
int main() {

    int i,T;
    bool Answer;
    ifstream in("perle.in");
    ofstream out("perle.out");

    in>>T;

    while(T--) {

        in>>N;

        for(i=1;i<=N;i++)
            in>>V[i];

        Answer=(A(1)==N)|(B(1)==N)|(C(1)==N);

        out<<Answer<<'\n';

        }

    in.close();
    out.close();

    return 0;

}