#include <fstream>
#include <deque>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int t, n;
char v[10001];
bool is_a(char ch)
{
    return ch=='1' || ch=='2' || ch=='3';
}
int dist(int st, int dr)
{
    return dr-st+1;
}
bool solve()
{
    int ind=1;
    for(int i=1; i<=n; i++)
        fin >> v[i];
    deque<char>q;
    if(dist(ind, n)==1)
        return 1;
    if(dist(ind, n)==3 && v[1]=='1' && v[2]=='2' && is_a(v[3]))
        return 1;
    if(dist(ind, n)>=5 && v[1]=='1' && is_a(v[2]) && v[3]=='3' && is_a(v[4]))
        ind+=4, q.push_back('C');
    if(dist(ind, n)>=2 && v[1]=='2')
        ind++, q.push_back('B');
    if(dist(ind, n)>=3 && v[1]=='3')
        ind++, q.push_back('B'), q.push_back('C');
    while(!q.empty())
    {
        char top=q.front();
        q.pop_front();
        if(top=='A')
            ind++;
        else if(top=='C' && v[ind]=='2')
            ind++;
        else if(top=='C' && v[ind]=='1' && v[ind+1]=='2' && is_a(v[ind+2]))
            ind+=3;
        else if(top=='B' && dist(ind, n)>=2 && v[ind]=='2')
            ind++, q.push_front('B');
        else if(top=='B' && dist(ind, n)>=5 && v[ind]=='1' && is_a(v[ind+1]) && v[ind+2]=='3' && is_a(v[ind+3]))
            ind+=4, q.push_front('C');
        else if(top=='C' && dist(ind, n)>=3 && v[ind]=='3')
            ind+=1, q.push_front('C'), q.push_front('B');
        if(ind==n+1)
            return 1;
    }
    return 0;
    
}
int main()
{
    fin >> t;
    for(int i=1; i<=t; i++)
        fin >> n, fout << solve() << "\n";
    return 0;
}