#include<fstream>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int V[10005], L, T, pos;
bool ok;

void solve_B();
void solve_C();

void solve_B(){
    if( ok == false )
        return;
    if( pos > L ){
        ok = false;
        return;
    }
    if( V[pos] == 2 ){
        pos++;
        solve_B();
        return;
    }
    if( V[pos] == 1 ){
        if( pos + 4 <= L && V[pos + 2] == 3 ){
            pos += 4;
            solve_C();
            return;
        }
    }
    ok = false;
    return;
}

void solve_C(){
    if( ok == false || pos > L )
        return;
    if( pos <= L && V[pos] == 2 ){
        pos++;
        return;
    }
    if( V[pos] == 3 ){
        pos++;
        solve_B();
        solve_C();
        return;
    }
    if( pos + 2 <= L && V[pos] == 1 && V[pos + 1] == 2 ){
        pos += 3;
        return;
    }
    ok = false;
    return;
}

int main(){
    fin >> T;
    for( int t = 1; t <= T; t++ ){
        fin >> L;
        for( int i = 1; i <= L; i++ )
            fin >> V[i];
        if( L == 1 ){
            fout << "1\n";
            continue;
        }
        pos = 1;
        ok = true;
        if( V[1] == 2 )
            solve_B();
        if( V[1] == 3 )
            solve_C();
        if( V[1] == 1 ){
            if( L < 3 )
                ok = false;
            if( L == 3 ){
                if( V[1] == 1 && V[2] == 2 )
                    pos = L + 1;
                else
                    ok = false;
            }
            if( L == 4 )
                ok = false;
            if( L >= 5 )
                solve_B();
        }
        if( ok == true && pos > L )
            fout << "1\n";
        else
            fout << "0\n";
    }
    return 0;
}