#include <fstream>
 
 
using namespace std;
 
int lungime;
 
char sir[10001];
int n;
 
int c(int poz);
 
int b(int poz)
{
   if(poz>lungime) 
      return 0;  
          
   if(sir[poz]=='2')
   {
         return b(poz+1);                 
   }
   else if(sir[poz]=='1' && sir[poz+2]=='3')
   {
      return c(poz+4);     
   }  
    
   return 0;
}
 
int aux;
 
int c(int poz)
{
   if(poz>lungime)
     return 0;
       
   if(sir[poz]=='2')
     return poz;
   else if(sir[poz]=='1' && sir[poz+1]=='2')
     return (poz+2);
   else if(sir[poz]=='3')
   {
      aux=b(poz+1);
      
      if(aux!=0)
         return c(aux+1);
   }
    
   return 0;
}
 
int main()
{
    ifstream fin("perle.in");
    ofstream fout("perle.out");
    
    int n;
    fin>>n;
     
    int contor,i;
     
    for(contor=0;contor<n;contor++)
    {
        fin>>lungime;
     
        for(i=1;i<=lungime;i++)
           fin>>sir[i]; 
           
        if(lungime==1)
        { 
           fout<<"1\n";
        }
        else if((b(1)==lungime) || (c(1)==lungime))
        { 
           fout<<"1\n";    
        }
        else
        { 
           fout<<"0\n";    
        }
    }
    
    fin.close();
    fout.close();
    return 0;
}