#include<fstream> 
using namespace std; 
ofstream g("perle.out"); 
int a[10005],n; 
int b(int i); 
int c(int i); 
int verif(){     
if(n==1)         
return 1;     
if(n==2)       
return 0;  
if(a[1]==3)   
return c(1); 
if(a[1]==1)  
if(c(1))  
return 1; 
return b(1); 
}
int b(int i){ 
if(a[i]==2)   
return b(i+1); 
if(a[i]==1 && a[i+2]==3) 
return c(i+4); 
return c(i+1); 
}
int c(int i){   
if(a[i]==2 && i==n)return 1; 
if(a[i]==2) return c(i+1); 
if(a[i]==3) return b(i+1); 
if(a[i]==1 && a[i+1]==2 && i+2==n) return 1;
if(a[i]==1 && a[i+1]==2) return c(i+3); 
return 0; 
} 
int main(){ 
int t; 
ifstream f("perle.in"); 
f>>t; 
while(t>0){      
f>>n;     
for(int i=1;i<=n;i++)          
f>>a[i];     
g<<verif()<<endl;       
t--;   
}   
return 0;
}