#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'){
    (*poz)++;
    if(*poz == len)  return 1;
    return 2;
  }
  if(sir[*poz] == '3'){
    int r1, r2;
    *poz += 1;
    r1 = B(poz, len);
    r2 = C(poz, len);
    return min2(r1, r2);
  }
  if(sir[*poz] == '1' && sir[(*poz) + 1] == '2'){
    *poz += 3;
    if(*poz == len) return 1;
    return 2;
  }
  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);
      if(r1 == 2) r1 = 0;
      poz = 0;
      r2 = C(&poz, l);
      if(r2 == 2) r2 = 0;
      fprintf(out, "%d\n", max2(r1, r2));
    }

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