#include <bits/stdc++.h>

#define __NAME_OF_THE_FILE__ "perle"

int pearls[10005];
size_t checkB(size_t i);
size_t checkC(size_t i);

/*
  B :=   2B   |
         1A3AC
*/
size_t checkB(size_t i) {
  // we treat the first case ( B := 2B )
  if (pearls[i] == 2) {
    return checkB(i + 1);
  }

  // we treat the second case ( B := 1A3AC )
  if (pearls[i] == 1) {
    if (pearls[i + 2] == 3) {
      // there is no need to verify if the second and
      // the fourth element came from an A, so we check for C
      return checkC(i + 4);
    }
  }

  return 0;
};

/*
  C :=   2   |
         3BC |
         12A
*/
size_t checkC(size_t i) {
  // we treat the first case ( C := 2 )
  if (pearls[i] == 2) {
    return i + 1;
  }

  // we treat the second case ( C := 1BC )
  if (pearls[i] == 3) {
    // the checkC function gets from checkB the index of where the
    // B subarray ends ( so, where the C subarray starts ) and tries to find
    // where the string of pearls that came from a C end
    return checkC(checkB(i + 1));
  }

  // we treat the third case ( C := 12A )
  if (pearls[i] == 1) {
    if (pearls[i + 1] == 2) {
      return i + 3;
    }
  }

  return 0;
};

int main() {
  freopen(__NAME_OF_THE_FILE__ ".in", "r", stdin);
#ifdef INFOARENA
  freopen(__NAME_OF_THE_FILE__ ".out", "w", stdout);
#endif

  // read the tests
  size_t testCount;
  scanf("%zu", &testCount);
  while (testCount--) {
    // read the string of pearls
    size_t pearlsCount;
    scanf("%zu", &pearlsCount);
    for (size_t i = 0; i < pearlsCount; i++) {
      scanf("%i", &pearls[i]);
    }

    // solve the test
    if (pearlsCount == 1) {
      // magic pearl A can tranform itself in just *one* normal pearl, this
      // means that if the pearlsCount == 1, the normal pearl was from an A
      printf("1\n");
      continue;
    } else if (checkB(0) == pearlsCount) {
      // here we check if the string of pearls came from a B
      // *see [footnote 1] for details about the functions' (checkB and checkC)
      // parameter and return value
      printf("1\n");
    } else if (checkC(0) == pearlsCount) {
      // and here we check if it came from a C
      printf("1\n");
      continue;
    } else {
      // if the string of pearls did not came from A, B or C, then we write '0'
      // to the file
      printf("0\n");
    }

    // reset the pearls string
    memset(pearls, 0, pearlsCount);
  }

  return 0;
}

/** footnotes
 * [footnote 1]
 * ```checkB()``` and ```checkC()``` both are very similar. They
 * traverse the ```pearls``` array in order to find where the subarray of pearls
 * that came from a B (or a C) ends. The parameter ```i``` (which stands for
 * index) shows the function from where to begin the search. They return the
 * index where the subarray ends plus 1.
 *
 * For example: we apply checkB(2) on this array of pearls:
 *          elements:               3 3 1 1 3 1 2 4
 *          index of the elements:  0 1 2 3 4 5 6 7
 * The search starts from index 2:      ^i (start index)
 *
 * We know that the subarray that
 * started from index 2 and came
 * from a magic pearl B ends at index 6:        ^ (where the subarray ends)
 *
 * so, the function will return 6 plus 1 = 7      ^ return value (where the
 *                                                         subarray ends plus 1)
 */