#include<fstream>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int M, N, v[10005], pos;
int B();
int C();
int B(){
    if( pos > N )
        return 0;
    if( v[pos] == 2 ){
        pos++;
        return B();
    }
    if( v[pos] == 1 ){
        if( N - pos + 1 >= 5 && v[pos] == 1 && v[pos + 2] == 3 ){
            pos += 4;
            return C();
        }
    }
    return 0;
}
int C(){
    if( v[pos] == 2 && pos == N )
        return 1;
    if( v[pos] == 3 ){
        pos++;
        if( B() == 0 ){
            pos++;
            return C();
        }
        return 0;
    }
    if( v[pos] == 1 && pos + 2 == N && v[pos + 1] == 2 )
        return 1;
    return 0;
}
int main(){
    fin >> M;
    for( int i = 1; i <= M; i++ ){
        fin >> N;
        for( int j = 1; j <= N; j++ )
            fin >> v[j];
        if( N == 1 ){
            fout << "1\n";
            continue;
        }
        pos = 1;
        if( B() == 1 )
            fout << "1\n";
        else
            if( C() == 1 )
                fout << "1\n";
            else
                fout << "0\n";
    }
    return 0;
}