#include <bits/stdc++.h>
#define NM 10005
using namespace std;
ifstream fin ("perle.in");
ofstream fout ("perle.out");
int Q, n;
bitset<NM> a;
short b[NM], c[NM];
bitset<NM> viza, vizb, vizc;
char aux[NM], s[NM];
int B(int i);
int C(int i)
{
    if(vizc[i])
        return c[i];
    vizc[i] = 1;
    if(s[i] == '2')
        return (c[i] = 1);
    if(i >= n-2)
        return 0;
    if(s[i] == '1' && s[i+1] == '2')
        return (c[i] = 3);
    if(s[i] == '3')
    {
        int aux = B(i+1), aux2;
        if(!aux)
            return 0;
        else
        {
            aux2 = C(i+aux+1);
            if(!aux2)
                return 0;
            return aux2+aux+1;
        }
    }
}
int B(int i)
{
    if(vizb[i])
        return b[i];
    vizb[i] = 1;
    if(i >= n-1)
        return 0;
    int aux = B(i+1);
    if(s[i] == '2' && aux)
        return (b[i] = 1+aux);
    if(i > n-5)
        return 0;
    aux = C(i+4);
    if(s[i] == '1' && s[i+2] == '3' && aux)
        return (b[i] = 4+aux);
    return 0;
}
int main()
{
    fin >> Q;
    fin.get();
    while(Q--)
    {
        fin >> n;
        fin.getline(aux, NM);
        for(int i=1; aux[i]; i+=2)
            s[i/2] = aux[i];
        /*
        for(int i=0; s[i]; ++i)
            fout << s[i];
        fout << '\n';
        */
        for(int i=0; i<=n; i++)
            viza[i] = vizb[i] = vizc[i]
            = a[i] = b[i] = c[i] = 0;
        if(B(0) == n || C(0) == n || n == 1)
            fout << "1\n";
        else fout << "0\n";
    }
    return 0;
}