#include <stdio.h>

#define NMAX 10000

char sir[NMAX + 2];
int n, p;

char posibil( char op ) {
  if ( p == n )
    return 0;
  if ( op == 'B' ) {
    if ( sir[p] == '3' )
      return 0;
    if ( sir[p] == '2' ) {
      if ( n - p <= 1 )
        return 0;
      p++;
      return posibil( 'B' );
    }
    /// sir[p] == '1'
    if ( n - p <= 4 )
      return 0;
    if ( sir[p + 2] != '3' )
      return 0;
    p += 4;
    return posibil( 'C' );
  } else { /// op == 'C'
    if ( sir[p] == '2' ) {
      if ( p == n - 1 )
        return 0;
      p++;
      return 1;
    }
    if ( sir[p] == '1' ) {
      if ( n - p <= 2 )
        return 0;
      if ( sir[p + 1] != '2' )
        return 0;
      p += 3;
      return 1;
    }
    /// sir[p] == '3'
    if ( n - p <= 2 )
      return 0;
    p++;
    char aux = posibil( 'B' );
    return (aux + posibil( 'C' )) > 0;
  }
}

int main() {
  FILE *fin, *fout;
  int t, i, aux;

  fin = fopen( "perle.in", "r" );
  fout = fopen( "perle.out", "w" );
  for ( fscanf( fin, "%d", &t ); t > 0; t-- ) {
    fscanf( fin, "%d ", &n );
    for ( i = 0; i < n; i++ )
      fscanf( fin, "%c ", &sir[i] );
    if ( n == 1 ) {
      fprintf( fout, "1\n" );
    } else {
      p = 0;
      aux = (posibil( 'B' ) == 1 && p == n);
      p = 0;
      fprintf( fout, "%d\n", (aux + (posibil( 'C' ) == 1 && p == n)) > 0 );
    }
  }
  fclose( fin );
  fclose( fout );

  return 0;
}