#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

string s;
int T, poz, NrCaractere;
bool isB(), isC();

void eliminateSpaces() {
    NrCaractere = s[0] - '0';
    s.erase(0, 1);
    for (int i = 0; i < NrCaractere; ++i) {
        if (s[i] == ' ')
            s.erase(i, 1);
    }
}

bool isB() {
    if (poz > NrCaractere - 5) return false;//nu ajung caracterele ramase, deci nu pot forma B
    if (s[poz] == '2') {
        ++poz;
        return isB();
    }else
    if (s[poz] == '1' && s[poz + 2] == '3') {
        poz += 4;
        if (s[poz++] == '2')
            return true;
        else if (isC())
            return true;
        return false;
    }
    return false;
}

bool isC() {
    if (s[poz] == '2') {
        ++poz;
        return true;
    }
    if (s[poz] == '3') {
        ++poz;
        return isB() && isC();
    }
    if (poz <= NrCaractere - 3 && s[poz] == '1' && s[poz + 1] == '2') {
        poz += 3;
        return true;
    }
    return false;
}

int main() {
    fin >> T;
    getline(fin, s);
    while (T--) {
        getline(fin, s);
        eliminateSpaces();
        poz = 0;
        if (s.length() == 1)//se poate forma din A
            fout << 1;
        else//nu se poate forma din A, deci trebuie sa vedem daca se poate forma din B sau C
        if (isB())
            fout << 1;
        else {
            poz = 0;
            if (isC() && poz == NrCaractere)
                fout << 1;
            else fout << 0;
        }
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}