#include <bits/stdc++.h>
using namespace std;
ifstream fin("sir10.in");
ofstream fout("sir10.out");

int n, ok, fals, p;
char s[10001], c[10001];
char b1[]="2B", b2[]="1A3AC";
char c1[]="2", c2[]="3BC", c3[]="12A";

void stergere()
{
    for(int i=strlen(s)-1; i>=0; i--)
        s[i]=0;
}

int main()
{
	fin>>n;
	//fin.get();
	while(n)
	{
		//fin.getline(s, 10000);
		//stergere();
		fin>>p;
		s[p]=0;
		for(int i=0; i<p; i++)
		{
		    char k;
		    fin>>k;
		    s[i]=k;
		}
		//fout<<s<<"\n";
		if(strlen(s)==1)
			fout<<1<<"\n";
		else if(strlen(s)==2)
		    fout<<0<<"\n";
		else
		{
		    //fout<<s;
		    ok=0;
			for(char st='B'; st<='C' && !ok; st++)
			{
			    fals=0;
			    if(st=='B')
			    {
			        if(s[0]=='1')
			            strcpy(c, b2);
			        else if(s[0]=='2')
			            strcpy(c, b1);
			        else
			            fals=1;//continue;
			        //cout<<s[0];
			        //cout<<strlen(c)<<" "<<strlen(s)<<"\n";
                    while(strlen(c)<strlen(s) && !fals)
                    {

                        for(int i=0; i<strlen(c) && !fals; i++)
                        {
                            //cout<<c[i]<<" "<<s[i]<<"\n";
                            if(c[i]==s[i])
                                continue;
                            else if(c[i]=='A')
                                c[i]=s[i];
                            else if(c[i]=='B' && s[i]=='2')
                            {
                                char aux[10001];
                                strcpy(aux, c+i+1);
                                strcpy(c+i, b1);
                                strcat(c, aux);
                                //cout<<c<<"\n";
                            }
                            else if(c[i]=='B' && s[i]=='1')
                            {
                                char aux[10001];
                                strcpy(aux, c+i+1);
                                strcpy(c+i, b2);
                                strcat(c, aux);
                                //cout<<c<<"\n";
                            }
                            else if(c[i]=='C' && s[i]=='2')
                                c[i]=s[i];
                            else if(c[i]=='C' && s[i]=='3')
                            {
                                char aux[10001];
                                strcpy(aux, c+i+1);
                                strcpy(c+i, c2);
                                strcat(c, aux);
                            }
                            else if(c[i]=='C' && s[i]=='1')
                            {
                                char aux[10001];
                                strcpy(aux, c+i+1);
                                strcpy(c+i, c3);
                                strcat(c, aux);
                                //cout<<c<<"\n";
                            }
                            else
                                fals=1;
                            //cout<<c<<"\n";

                        }
                        if(strlen(c)!=strlen(s))
                            fals=1;
                    }
			    }
			    else
			    {
			        //cout<<1;
			        if(s[0]=='2')
			            fals=1;
			        else if(s[0]=='1')
			            strcpy(c, c3);
			        else if(s[0]=='3')
			            strcpy(c, c2);
			        while(strlen(c)<strlen(s) && !fals)
                    {
                        for(int i=0; i<strlen(c) && !fals; i++)
                        {
                            if(c[i]==s[i])
                                continue;
                            else if(c[i]=='A')
                                c[i]=s[i];
                            else if(c[i]=='B' && s[i]=='2')
                            {
                                char aux[10001];
                                strcpy(aux, c+i+1);
                                strcpy(c+i, b1);
                                strcat(c, aux);
                            }
                            else if(c[i]=='B' && s[i]=='1')
                            {
                                char aux[10001];
                                strcpy(aux, c+i+1);
                                strcpy(c+i, b2);
                                strcat(c, aux);
                            }
                            else if(c[i]=='C' && s[i]=='2')
                                c[i]=s[i];
                            else if(c[i]=='C' && s[i]=='3')
                            {
                                char aux[10001];
                                strcpy(aux, c+i+1);
                                strcpy(c+i, c2);
                                strcat(c, aux);
                            }
                            else if(c[i]=='C' && s[i]=='1')
                            {
                                char aux[10001];
                                strcpy(aux, c+i+1);
                                strcpy(c+i, c3);
                                strcat(c, aux);
                            }
                            else
                                fals=1;
                        }
                        if(strlen(c)!=strlen(s))
                            fals=1;
                    }
			    }
			    if(fals==0)
			        ok=1;
			}
			fout<<ok<<"\n";
		}
		n--;
	}

	return 0;
}