#include <fstream>
#include <string.h>
using namespace std;

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

int l, n; char str[15];

bool verif()
{
        TOP:
        for(int i=n-1; i>3; i--)
        {
            if((str[i]=='C'||str[i]=='2')&&(str[i-1]=='1'||str[i-1]=='2'||str[i-1]=='3')&&str[i-2]=='3'&&(str[i-3]=='1'||str[i-3]=='2'||str[i-3]=='3')&&str[i-4]=='1')
            {
                str[i-4]='B';
                n-=4;
                for(int j=i-3; j<n; j++)
                    str[j]=str[j+3];
                goto TOP;
            }
        }
        for(int i=n-1; i>0; i--)
        {
            if(str[i]=='B'&&str[i-1]=='2')
            {
                str[i-1]='B';
                n--;
                for(int j=i; j<n; j++)
                    str[j]=str[j+1];
                goto TOP;
            }
        }
        for(int i=n-1; i>1; i--)
        {
            if((str[i]=='1'||str[i]=='2'||str[i]=='3')&&str[i-1]=='2'&&str[i-2]=='1')
            {
                n-=2;
                str[i-2]='C';
                for(int j=i-1; j<n; j++)
                    str[j]=str[j+2];
                goto TOP;
            }
            else if((str[i]=='C'||str[i]=='2')&&str[i-1]=='B'&&str[i-2]=='3')
            {
                n-=2;
                str[i-2]='C';
                for(int j=i-1; j<n; j++)
                    str[j]=str[j+2];
                goto TOP;
            }
        }
        if(n>1)
            return 0;
        return 1;
}

int main()
{
    f>>l;
    for(int i=0; i<l; i++)
    {
        f>>n;
        for(int j=0; j<n; j++)
            f>>str[j];
        g<<verif()<<endl;
    }
    return 0;
}