#include <bits/stdc++.h>
using namespace std;

int a[10012],i,n;
bool okok = 0;
bool A();
bool B();
bool C();

bool A(){
    if(i > n){
        return 0;
    }
    if(a[i] == 1 or a[i] == 2 or a[i] == 3){
        ++i;
        return 1;
    }
    return 0;
}

bool B(){
    if(i > n){
        return 0;
    }
    if(a[i] == 1){
        i++;
        if(A() == 0)return 0;
        //cout << i<< endl;
        if(a[i] == 3){
            i++;
            bool d = A();
           // cout << a[i+1] << endl;
            bool b = C();
            return (d && b);
        }
        //return 0;
    }else if(a[i] == 2){
        i++;
        return B();
    }
    return 0;
}

bool C(){
   // cout << "NICEE  " << a[i] << endl;
    if(i > n){
        return 0;
    }
    if(a[i] == 2){
        okok = 1;
        i++;
        return 1;
    }
    if(a[i] == 3){
        return B() && C();
    }
    if(a[i] == 1 && a[i+1] == 2){
       // cout << "HEREEE";
        i+=2;
        return A();
    }
    return 0;
}

int main(void){
    ofstream cout("perle.out");
    ifstream cin("perle.in");
    int T;
    cin >> T;
    while(T--){
        cin >>n;
        for(int j = 1;j<=n;j++){
            cin >> a[j];
        }
        a[n+1] = a[n+2] = a[n+3] = a[n + 4] = a[n+6] = a[n + 5] = 4;
        i = 1;
        if(A() && n == 1){
            cout << 1 << '\n';
            continue;
        }
        i = 1;
        if(B()){
            cout << 1 << '\n';
            continue;
        }
        i = 1;
        if(C()){
            if(okok && n > 1){
                cout << 0 << '\n';
                continue;
            }
            cout << 1 << '\n';
            continue;
        }
        cout << 0 << '\n';
    }
}