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

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

const int MAXN = 11, MAXL = 10001;

int N, ok;

void back(string s, string p)
{
    //cout<<s<<' '<<p<<endl;

    if( s.length() == 0 && p.length() == 0 )
    {
        ok = 1;
        return;
    }

    if( s.length() && s.length() <= p.length() )
    {

        if( p.length() >= 1 && s[ 0 ] == 'A' )
            back( s.substr( 1, s.size() - 1 ), p.substr( 1, p.size() - 1 ) );
        else if( s[ 0 ] == 'B' )
        {
            if( p.length() >= 2 && p[ 0 ] == '2' )
                back( s, p.substr( 1, p.size() - 1 ) );

            if( p.length() >= 5 && p[ 0 ] == '1' && p[ 2 ] == '3' )
            {
                s[ 0 ] = 'C';
                back( s, p.substr( 4, p.size() - 4 ) );
            }
        }
        else if( s[ 0 ] == 'C' )
        {
            if( p.length() >= 1 && p[ 0 ] == '2' )
                back( s.substr( 1, s.size() - 1 ), p.substr( 1, p.size() - 1 ) );

            if( p.length() >= 3 && p[ 0 ] == '3' )
            {
                s = 'B' + s;

                back( s, p.substr( 1, p.size() - 1 ) );
            }

            if( p.length() >= 3 && p[ 0 ] == '1' && p[ 1 ] == '2' )
                back( s.substr( 1, s.size() - 1 ), p.substr( 3, p.size() - 3 ) );
        }
    }

}

void solve()
{
    in>>N;

    for(int i = 1; i <= N; i++)
    {
        string s;
        int L;
        char c;
        ok = 0;

        in>>L;
        for(int i = 1; i <= L; i++)
        {
            in>>c;
            s += c;
        }

        string str = "A";

        back( str, s );

        if( ok == 0 )
        {
            str = "B";
            back( str, s );
        }

        if( ok == 0 )
        {
            str = "C";
            back( str, s );
        }

        out<<ok<<endl;
    }
}

int main()
{
    solve();

    return 0;
}