#include <stdio.h>
#include <string.h>

#define Lmax 10010

int T,L,i;
char s[Lmax],c;

void solve()
{
 int ok=1;
 while (ok)
	{
	 ok=0;
	 for (i=1;i<=L;++i)
	       {
		if ((i+4<=L)
		   &&
		   (s[i]=='1')
		   &&
		   ((s[i+1]=='1')||(s[i+1]=='2')||(s[i+1]=='3'))
		   &&
		   (s[i+2]=='3')
		   &&
		   ((s[i+3]=='1')||(s[i+3]=='2')||(s[i+3]=='3'))
		   &&
		   ((s[i+4]=='2')||(s[i+4]=='C')))
			{
			 s[i]='B';
			 memcpy(s+i+1,s+i+5,sizeof(char)*(L-i-4));
			 ok=1;
			 L-=4;
			 break;
			}
		if ((i+1<=L)
		   &&
		   (s[i]=='2')
		   &&
		   (s[i+1]=='B'))
			{
			 s[i]='B';
			 memcpy(s+i+1,s+i+2,sizeof(char)*(L-i-1));
			 ok=1;
			 --L;
			 break;
			}
		if ((i+2<=L)&&(s[i]=='3')&&(s[i+1]=='B')&&((s[i+2]=='C')||(s[i+2]=='2')))
			{
			 s[i]='C';
			 memcpy(s+i+1,s+i+3,sizeof(char)*(L-i-2));
			 ok=1;
			 L-=2;
			 break;
			}
		if ((i+2<=L)&&(s[i]=='1')&&(s[i+1]=='2')&&((s[i+2]=='1')||(s[i+2]=='2')||(s[i+2]=='3')))
			{
			 s[i]='C';
			 memcpy(s+i+1,s+i+3,sizeof(char)*(L-i-2));
			 ok=1;
			 L-=2;
			 break;
			}
	       }
	}
}

int main()
{
 freopen("perle.in","r",stdin);
 freopen("perle.out","w",stdout);
 scanf("%d",&T);
 while (T>0)
	{
	 --T;
	 scanf("%d",&L);
	 for (i=1;i<=L;++i)
		scanf(" %c",&s[i]);
	 solve();
	 if (L==1) printf("%d\n",1);
		else printf("%d\n",0);
	}
 fclose(stdin);
 fclose(stdout);
 return 0;
}