#include <fstream>
#include <stack>

using namespace std;

ifstream fi("perle.in");
ofstream fo("perle.out");

stack<char> stiva;

int sePoate(char* S, int L, char perla)
{
//  fo << "incerc " << perla << endl;
  while(!stiva.empty())
    stiva.pop();
  stiva.push(perla);
  int i = 0;
  while(i < L)
  {
    if(stiva.empty())
      return 0;

    char current = stiva.top();
//    fo << current << "-";
    stiva.pop();

    // we got a digit, if matches the current one, continue
    if(current == S[i] || current == 'A')
    {
      i++;
      continue;
    }

    if(current == 'B')
    {
      if(S[i] == '3') return 0;
      if(S[i] == '2')
      {
        stiva.push('B');
      }
      if(S[i] == '1')
      {
        stiva.push('C');
        stiva.push('A');
        stiva.push('3');
        stiva.push('A');
      }
      i++;
      continue;
    }

    if(current == 'C')
    {
      if(S[i] == '1')
      {
        stiva.push('A');
        stiva.push('2');
      }
      if(S[i] == '3')
      {
        stiva.push('C');
        stiva.push('B');
      }
      i++;
      continue;
    }
  }
  return stiva.empty();
}

int sePoate(char* S, int L)
{
  return sePoate(S, L, 'A') ||
         sePoate(S, L, 'B') ||
         sePoate(S, L, 'C');
}

int main(int argc, char *argv[])
{
  int N, L, c;
  fi >> N;
  char *S = new char[10001];
  for(int i = 0; i < N; i++)
  {
    fi >> L;
    for(int j = 0; j < L; j++)
    {
      fi >> c;
      S[j] = (char)c + '0';
    }
    fo << sePoate(S, L)
       << endl;
  }
  return 0;
}