#include <iostream>
#include <fstream>

using namespace std;

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

string C;

int rec(int p, char A) {

    if(p >= C.size())
        return C.size()+1;

    if(A == 'A') {
        return p+1;
    }

    if(A == 'B') {

        if(C[p] == '1') {

            if(p+4 >= C.size())
                return C.size()+1;

            if(C[p+2] != '3')
                return C.size()+1;

            return rec(p+4, 'C');

        }

        if(C[p] == '2') {
            if(p+1 >= C.size())
                return C.size()+1;
            return rec(p+1, 'B');
        }

        return p;

    }

    if(C[p] == '1') {

        if(p+2 >= C.size())
            return C.size()+1;

        if(C[p+1] != '2')
            return C.size()+1;

        return rec(p+2, 'A');

    }

    if(C[p] == '2') {
        return p+1;
    }

    if(C[p] == '3') {
        if(p+1 >= C.size())
            return C.size()+1;
        int T = rec(p+1, 'B');
        if(T >= C.size())
            return C.size()+1;
        T = rec(T, 'C');
        return T;
    }

}

int main() {

    string s;
    int n,t;
    in >> n;

    for(int i = 1; i <= n; i++) {
        in >> t;
        C = "";
        C.resize(t);
        for(int j = 0; j < t; j++)
            in >> C[j];
        if(rec(0, 'A') == t || rec(0, 'B') == t || rec(0, 'C') == t)
            out << "1" << '\n';
        else
            out << "0" << '\n';
    }

    return 0;
}