#include <stdio.h>
#define MAXL 10000

char sir[MAXL];
char B(int *poz, int len);
char C(int *poz, int len);
int max2(char a, char b){
  return a > b ? a : b;
}
int min2(char a, char b){
  return a > b ? b : a;
}
char B(int *poz, int len){
  if(*poz >= len)  return 0;
  if(sir[*poz] == '2'){
    *poz += 1;
    return B(poz, len);
  }
  if((*poz) + 4 >= len)  return 0;
  if(sir[*poz] == '1' && sir[(*poz) + 2] == '3'){
    *poz += 4;
    return C(poz, len);
  }
  return 0;
}
char C(int *poz, int len){
  if(*poz >= len)  return 0;
  if(sir[*poz] == '2'){
    if(*poz == len - 1)  return 1;
    return 0;
  }
  if(sir[*poz] == '3'){
    *poz += 1;
    return min2(B(poz, len), C(poz, len));
  }
  if(sir[*poz] == '1' && sir[(*poz) + 1] == '2'){
    if((*poz) + 2 == len - 1) return 1;
    return 0;
  }
  return 0;
}



int main(){
  FILE *in = fopen("perle.in", "r");
  FILE *out = fopen("perle.out", "w");
  int n;
  fscanf(in, "%d", &n);
  int i, j, l, poz;
  char r1, r2;
  for(i = 0; i < n; i++){
    fscanf(in, "%d ", &l);
    for(j = 0; j < l; j++){
      sir[j] = fgetc(in);
      fgetc(in);
    }
    if(l == 1)  fprintf(out, "1\n");
    else{
      poz = 0;
      r1 = B(&poz, l);
      poz = 0;
      r2 = C(&poz, l);
      fprintf(out, "%d\n", max2(r1, r2));
    }

  }
  fclose(in);
  fclose(out);
  return 0;
}