#include <stdio.h>
#include <stdlib.h>

#define MAXL 10000

int v[MAXL];

FILE *fin, *fout;

int procesare(int n, int first){
  int i, p, st = 1;
  i = 0;
  while((i < n) && (st == 1) && (first < MAXL)){
    fscanf(fin, "%d", &p);
    if(v[first] == 'B'){
      if(p == 1){
        if(4 < (n - i)){
          fscanf(fin, "%d%d", &p, &p);
          if(p == 3){
            fscanf(fin, "%d", &p);
            v[first] = 'C';
            i += 4;
          }else{
            st = 0;
          }
        }else{
          st = 0;
        }
      }else if(p == 2){
        i++;
      }else{
        st = 0;
      }
    }else{
      if(p == 1){
        if(3 <= (n - i)){
          fscanf(fin, "%d", &p);
          if(p == 2){
            fscanf(fin, "%d", &p);
            i += 3;
          }else{
            st = 0;
          }
          first++;
        }else{
          st = 0;
        }
      }else if(p == 2){
        if(1 <= (n - i)){
          i++;
          first++;
        }else{
          st = 0;
        }
      }else{
        first--;
        v[first] = 'B';
        i++;
      }
    }
  }
  if((i == n) && (first == MAXL) && (st == 1)){
    return 1;
  }else{
    return 0;
  }
}

int main()
{
    int n, l, i, p, st;
    fin = fopen("perle.in", "r");
    fscanf(fin, "%d", &n);
    fout = fopen("perle.out", "w");
    for(i = 0; i < n; i++){
      fscanf(fin, "%d", &l);
      fscanf(fin, "%d", &p);
      st = 1;
      if(1 < l){
        if(p == 1){
          if(3 < l){
            fscanf(fin, "%d%d", &p, &p);
            if(p != 3){
              st = 0;
            }else{
              fscanf(fin, "%d", &p);
              v[MAXL - 1] = 'C';
              st = procesare(l - 4, MAXL - 1);
            }
          }else{
            if(l == 3){
              fscanf(fin, "%d", &p);
              if(p != 2){
                st = 0;
              }else{
                fscanf(fin, "%d", &p);
              }
            }else{
              st = 0;
            }
          }
        }else if(p == 2){
          v[MAXL - 1] = 'B';
          st = procesare(l - 1, MAXL - 1);
        }else{
          v[MAXL - 1] = 'C';
          v[MAXL - 2] = 'B';
          st = procesare(l - 1, MAXL - 2);
        }
      }else{
        st = 1;
      }
      fprintf(fout, "%d\n", st);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}