#include<cstdio>
char a[10005],k,l;

void rec(char c){
   if(k<l){ 
     if(c=='C'){
          if(a[k]=='2') ++k;    
          if(a[k]=='3' && k+2<l){
                        ++k;
                        rec('B');
                        rec('C');
                        }      
          if(a[k]=='1' && a[k+1]=='2' && k+2<l)
                        {
                         k+=2;
                         rec('A');   
                        }     
                }
     if(c=='B'){
                if(a[k]=='2' && k+1<l){
                              ++k;
                              rec('B');
                              } 
                 if(a[k]=='1' && k+4<l){
                               ++k;
                               rec('A');
                                 if(a[k]=='3'){
                                               ++k;
                                               rec('A');
                                               rec('C');                                              
                                               }                            
                               }                
                 }             
     if(c=='A'){
                if(a[k]=='1') ++k;  
                  else
                if(a[k]=='2') ++k; 
                  else
                if(a[k]=='3') ++k;            
                }
     }
}

int main(void){
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    int n,i; char ch;
    scanf("%d\n",&n);
    while(n--){
           scanf("%d",&l);
           for(i=0;i<l;++i)scanf(" %c",&a[i]);
           k=0;    
           rec('A');    
           if(k>=l)printf("1\n");
           else { 
                k=0; rec('B');
                if(k>=l)printf("1\n");
                else {
                     k=0;
                     rec('C');
                     if(k>=l)printf("1\n");
                       else printf("0\n");
                     }
                 }                          
               }   
 return 0;   
}