#include <fstream>
using namespace std;
ifstream in("perle.in");
ofstream out("perle.out");
int t,n,a[10001];
int perla_B(int i);
int perla_C(int i);
int perla_B(int i)
{ for(i;i<=n;i++)
    if(a[i]!=2)
       break;
  if(i==n+1)
     return 0;
  if(n<i+4)
     return 0;
  if(a[i]!=1 || a[i+2]!=3)
     return 0;
  return perla_C(i+4);
}
int perla_C(int i)
{ if(a[i]==2)       ///2
     return i+1;
  if(a[i]==1)       ///12A
  { if(n<i+2)
       return 0;
    if(a[i+1]==2)
       return i+3;
  }
  i=perla_B(i+1);    ///3BC
  if(i==n+1 || i==1)
     return 0;
  return perla_C(i);
}
int main()
{ in>>t;
  for(int i=1;i<=t;i++)
  { in>>n;
    for(int i=1;i<=n;i++)
      in>>a[i];
    if(n==1)
    { out<<"1\n";
      continue;
    }
    if(a[1]==1)
    { if(n==3 && a[2]==2)    ///12A
      { out<<"1\n";
        continue;
      }
      if(n>=5 && a[3]==3)    ///1A3AC
      { if(perla_C(5)==n+1)
           out<<"1\n";
        else
           out<<"0\n";
        continue;
      }
    }
    if(a[1]==2)              ///2B
    { if(perla_B(1)==n+1)
         out<<"1\n";
      else
         out<<"0\n";
      continue;
    }
    if(perla_C(1)==n+1)        ///3BC
       out<<"1\n";
    else
       out<<"0\n";
  }
  in.close();
  out.close();
  return 0;
}