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

int a[10012],i;

int A();
int B();
int C();

int A(){
    if(a[i] == 1 or a[i] == 2 or a[i] == 3){
        i++;
        return i;
    }
    return -1;
}
int B(){
    if(a[i] == 2){
        //cout << "HIHI";
        i++;
        if(B() != -1){
            //cout << i << endl;
            return i;
        }
    }else if(a[i] == 1){
        i++;
        if(A() != -1){
            //cout << a[i] << ' ' << i << endl << endl;
            if(a[i] == 3){
                i++;
                if(A() != -1 && C() != -1 ){
                  //  cout << i << ' ' << i << endl;
                    return i;

                }
            }
        }
    }
    return -1;
}

int C(){
    if(a[i] == 2){
       // cout << "PULA CU CACIULA" << endl;
        return i+1;
    }
    if(a[i] == 3){
        //cout << "HEHHE" << endl;
        i++;
        if(B() != -1 && C() != -1){
            return i+1;
        }
    }
    if(a[i] == 1 && a[i+1] == 2){
        //cout << "hehe ";
        //cout << a[i] << ' ' << i << ' ' << a[i+1] << ' ' << i + 1 << ' ' << a[i+2] << ' ' << endl;
        i+=2;
       // cout << i<< endl;
        if(A() != -1){
            //cout << i<< endl;
            return i+1;
        }
    }
    return -1;
}

int main(void){
    ofstream cout("perle.out");
    ifstream cin("perle.in");
    int T;
    cin >> T;
    while(T--){
        int n;
        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;
        //cout << A() << endl;
        if(A() == n+1 && n == 1){
            cout << 1 << '\n';
            continue;
        }
        i = 1;
        if(B() == n+1){
            cout << 1 << '\n';continue;
        }
        i = 1;
        if(C() == n + 1){
           cout << 1 << '\n';continue;
        }
        cout << 0 << '\n';
    }
}