#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 ((i+3==L)&&(s[i]=='1')&&(s[i+1]=='2')) return;
         else if ((i+1==L)&&(s[i]=='2')) 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') { i=4;solveC(); }
           else if (s[0]=='2') { i=1;solveB(); }
                else { i=1;solveB();solveC(); }
        printf("%d\n",ok);
       }
 fclose(stdin);
 fclose(stdout);
 return 0;
}