#include <iostream>
#include <cstdio>

using namespace std;

char perle[10002];

bool decodB(int p);
bool decodC(int p);

bool decodB(int p){
    if(perle[p] == '2')
        decodB(p + 1);
    if(perle[p] == '1'){
        if(perle[p + 2] != '3')
            return 0;
        decodC(p + 4);
    }
}

bool decodC(int p){
    if(perle[p] == '3'){
        if(decodB(p))
            return decodC(p + 1);
    }
    if((perle[p] == '1' && perle[p + 1] == '2') || perle[p] == '2')
        return 1;
    return 0;
}

int main()
{
    freopen("perle.in", "r", stdin);
    freopen("perle.out", "w", stdout);
    int t, n;
    scanf("%d", &t);
    for(int test = 1; test <= t; ++test){
        scanf("%d ", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%c ", &perle[i]);
        cerr << decodB(1) << " " << decodC(1) << "\n";
        if(decodB(1) || decodC(1))
            printf("1\n");
        else
            printf("0\n");
    }
    return 0;
}