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

FILE*f=fopen("perle.in","r");
FILE*g=fopen("perle.out","w");

int a[10010],i,k,l,n;

int perlaB(int k);
int perlaC(int k);

int perlaB(int k) 
{
    if(a[k]==1 && a[k+2]==3) return perlaC(k+4); //B -> 1A3AC
    if(a[k]==2) return perlaB(k+1); // B -> 2B
    return 0;
}

int perlaC(int k) 
{
    if(a[k]==1 && a[k+1]==2) return k+2; // C -> 12A
    if(a[k]==2) return k;  // C -> 2
    if(a[k]==3) return perlaC(perlaB(k+1)+1); // C -> 3BC
    return 0;
}

int main()
   {

    fscanf(f,"%d",&n);
    for(k=1;k<=n;k++) {
        fscanf(f,"%d",&l);
        for(i=1;i<=l;i++) fscanf(f,"%d",&a[i]);
        // Daca lungimea sirului obtinut  = l afiseaza 1
        if(l==1 || perlaB(1)==l || perlaC(1)==l) fprintf(g,"%d\n",1);
        else fprintf(g,"%d\n",0);
    }

    fclose(f); fclose(g);

    return 0;
}