#include<cstdio>
#include<deque>
using namespace std;
deque<int>dq;
int v[10005];
int trys(int num,int n){
int poz=1,nr;
dq.clear();
dq.push_back(num);
while(!dq.empty() && poz<=n){
nr=dq.front();
if (nr==-2){
if (v[poz]==3)
return 0;
if (v[poz]==2){
poz++;
continue;}
if (v[poz]==1 && v[poz+2]==3){
poz=poz+4;
dq.pop_front();
dq.push_front(-3);
continue;}
return 0;}
if (nr==-3){
if (v[poz]==2){
poz++;
dq.pop_front();
continue;}
if (v[poz]==1 && v[poz+1]==2){
poz=poz+3;
dq.pop_front();
continue;}
if (v[poz]==3){
poz++;
dq.pop_front();
dq.push_front(-3);
dq.push_front(-2);
continue;}
return 0;}}
if (!dq.empty() || poz!=n+1)
return 0;
return 1;}
int main(){
freopen("perle.in","r",stdin);
freopen("perle.out","w",stdout);
int t,i1,n,i;
scanf("%d",&t);
for(i1=1;i1<=t;i1++){
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
if (n==1){
printf("1\n");
continue;}
if (trys(-2,n))
printf("1\n");
else
if (trys(-3,n))
printf("1\n");
else
printf("0\n");}
return 0;}