#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){
        i++;
        if(B() != -1){
            return i;
        }
    }else if(a[i] == 1){
        i++;
        if(A() != -1){
            if(a[i] == 3){
                i++;
                if(A() != -1 && C() != -1 ){
                    return i;
                }
            }
        }
    }
    return -1;
}

int C(){
    if(a[i] == 2){
        return i+1;
    }
    if(a[i] == 3){
        i++;
        if(B() != -1){
            return i;
        }
    }
    if(a[i] == 1 && a[i+1] == 2){
        i+=2;
        if(A() != -1){
            return i;
        }
    }
    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;
        if(A() == 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';
    }
}