#include <fstream>

using namespace std;

ifstream cin("perle.in");
ofstream cout("perle.out");

const int lmax = 1e4 + 1;

int l, idx, v[lmax];

void b();
void c();

void b(){
    if(idx > l)
        return;
    if(v[idx] == 2){
        ++idx;
        b();
    }
    else if(v[idx] == 1 && v[idx + 2] == 3 && idx + 4 <= l){
        idx += 4;
        c();
    }
}

void c(){
    if(idx > l)
        return;
    if(v[idx] == 2)
        return;
    else if(v[idx] == 1 && v[idx + 1] == 2 && idx + 2 == l){
        idx += 2;
        return;
    } else if(v[idx] == 3){
        ++idx;
        b();
        ++idx;
        c();
    }
}

void solve(){
    cin >> l;

    for(int i = 1; i <= l; i++)
        cin >> v[i];

    if(l == 1)
        {cout << "1\n"; return;}

    idx = 1;

    if(v[1] == 1){
        if(l == 3)
            c();
        else
            b();
    } else if(v[1] == 2)
        b();
    else
        c();

    cout << (idx == l) << "\n";
}

int main()
{
    int n;

    cin >> n;

    for(int i = 1; i <= n; i++)
        solve();

    return 0;
}