#include <cstdio>
using namespace std ;
//       A -> 1 | 2 | 3
//       B -> 2B | 1A3AC
//       C -> 2 | 3BC | 12A
// 

// B->1A3AC->1131C->11313BC->113131A3ACC->113131131CC->11313113122 

static
bool match ( int * x , int n ) {
  if ( 0 >= n ) return false ;                                 // 0- : $
  if ( 1 == n ) return true  ;                                 // 1  : "#"
  if ( 2 == n ) return false ;                                 // 2 : $
  if ( 3 == n ) return 1 == x [0] && 2 == x [1] ;              // 3 : "12#"
  if ( 4 == n ) return false ;                                 // 4 :  $
  if ( 5 == n ) return 1 == x [0] && 3 == x [2] && 2 == x [4] ;// 5 : "1#3#2"
  bool c =   ( 3 == x [0] ) ;
  bool b = ! c ;
  int k = 0 , m = 1 ;
  while ( n > k ) {
    if (b) {
      if ( 2 == x [k] ) { // B->2B
        ++ k ;
        continue ; // need B
      }
      if ( 1 == x [k] ) { // B->1A3AC
        if ( 4 + k >= n || 3 != x [2+k]) return false ;
        k += 4 ;  b = false ; c = true ;
        continue ; // need C
      }
    } // needed B
    if (c) {
      if ( 2 == x [k] ) { // C->2
    	k += 1 ;
        -- m ; if (0 > m) return false ; if ( 0 == m ) c = false ;
        continue ; // need C or end of string
      }
      if ( 3 == x [k] ) { // C --> 3BC
        m += 1; k += 1; c = false; b = true;
        continue ;  // need B
      }
      if ( 1 == x [k] ) { // C ->12A
        if (2 + k >= n || 2 != x[1+k]) return false ;
        k += 3 ;
        -- m ; if ( 0 > m ) return false ; if ( 0 == m ) c = false ;
        continue ; // need C or nothing
      }
    } // needed C
    return false ;
  }
  return ! ( b || c );
}

#define S(v) scanf("%d", &v);
#define P(v) printf("%d\n", v);

int
main ( ) {
  freopen ( "perle.in" , "r" , stdin ) ;
  freopen ( "perle.out" , "w" , stdout ) ;
  setvbuf(stdin, NULL, _IOFBF, 4 * 1024 * 1024 ) ;
  setvbuf(stdout, NULL, _IOFBF, 4 * 1024 * 1024 ) ;
  int const MAXN = 10001 ;
  int q, n, i, j ;
  int v [ MAXN ] ;
  S (q) ;
  for ( i = 0 ; i < q ; i ++ ) {
    S(n) ;
    for ( j = 0 ; j < n ; j ++ ) S (v[j]);
    P (match(v, n) ? 1 : 0 ) ;
  }
  return 0 ;
}