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

#define Lmax 10010

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

void solveC();

void solveB()
{
 while ((i<L)&&(s[i]=='2')) ++i;
 if (i>=L) { ok=0;return; }
  else if ((s[i]=='1')&&(s[i+2]=='3')) { i+=4;solveC(); }
       else { ok=0;return; }
}

void solveC()
{
 if (i>=L) { ok=0;return; }
 if (s[i]=='3') { ++i;solveB();solveC(); }
    else if ((s[i]=='1')&&(s[i+1]=='2')) { i+=3;return; }
         else if (s[i]=='2') { ++i;return; }
              else { ok=0;return; }
}

int main()
{
 freopen("perle.in","r",stdin);
 freopen("perle.out","w",stdout);
 scanf("%d",&T);
 while (T)
       {
        --T;
        scanf("%d",&L);
        for (i=0;i<L;++i)
           	scanf(" %c",&s[i]);
        if ((L==1)||((L==3)&&(s[0]=='1')&&(s[1]=='2'))) { printf("1\n");continue; }
        ok=1;
        if ((s[0]=='1')&&(s[2]=='3')) { i=4;solveC(); }
           else if (s[0]=='2') { i=1;solveB(); }
                else if (s[0]=='3') { i=1;solveB();solveC(); }
                     else ok=0;
        if (i!=L) ok=0;
        printf("%d\n",ok);
       }
 fclose(stdin);
 fclose(stdout);
 return 0;
}