//Problema se rezolva prin metoda recursivitatii indirecte, functiile b si c intorc numarul de pozitii cu care se inainteaza
//folosind o perla de tipul B sau una de tipul C, daca se inainteaza cu exact lungimea sirului inseamna clar ca sirul
//poate fi obtinut. O solutie putin mai eficienta se poate obtine parsand datele de intrare desi aceasta sursa obtine
//maxim 4ms pe teste, deci nu are rost sa implementam parsarea datelor de intrare.
#include <fstream>
 
using namespace std;

//Lungimea sirului de perle curent 
int lungime;

//Sirul curent de perle 
char sir[10001];

//Numarul de siruri de perle
int n;

//Deoarece vom folosi tehnica recursivitatii indirecte, avem nevoie de prototipul functiei c 
int c(int poz);

//Functia intoarce cat de mult se poate merge in fata daca la pozitia poz se afla c sau 0 daca toate variantele
//de a merge in fata duc la esec 
int b(int poz)
{
   //Daca se iese din sir, clar am esuat
   if(poz>lungime) 
      return 0;  
   
   //Avem doua cazuri       
   if(sir[poz]=='2') //2B
   {
         return b(poz+1);                 
   }
   else if(sir[poz]=='1' && sir[poz+2]=='3') //1A3AC - A-urile nu conteaza, caci pot fi orice
   {
      return c(poz+4);     
   }  
   
   //Daca nu ne incadram in aceste doua cazuri, am esuat 
   return 0;
}

//Variabila auxiliara 
int aux;
 
int c(int poz)
{ 
   //Daca se iese din sir, clar am esuat
   if(poz>lungime)
     return 0;
   
   //Daca putem pune un 2, atunci suntem intr-un caz terminal si putem sa intoarcem pozitia la care am ajuns    
   if(sir[poz]=='2')
     return poz;
   else if(sir[poz]=='1' && sir[poz+1]=='2') //Daca nu, avem doua cazuri: 12A
     return (poz+2);
   else if(sir[poz]=='3') //si 3BC, caz mai complicat deoarece B-ul se poate extinde destul de mult
   {
      aux=b(poz+1);
      
      //Daca nu am asuat cu B-ul, atunci continuam cu C-ul
      if(aux!=0)
         return c(aux+1);
   }
   
   //Daca nu ne incadram in cazurile de mai sus, am asuat 
   return 0;
}
 
int main()
{
    //Deschiderea fisierelor de intrare si iesire
    ifstream fin("perle.in");
    ofstream fout("perle.out");
    
    //n, numarul de siruri cu perle, este declarat si citit
    int n;
    fin>>n;
    
    //contor si i sunt doua contoare 
    int contor,i;
     
    for(contor=0;contor<n;contor++)
    {
        //Citim sirul curent                           
        fin>>lungime;
     
        for(i=1;i<=lungime;i++)
           fin>>sir[i]; 
        
        //Solutionam problema   
        if(lungime==1) //Un sir de lungime 1 se poate obtine dintr-o perla magica de tipul A
        { 
           fout<<"1\n";
        }
        else if((b(1)==lungime) || (c(1)==lungime)) //Daca sirul nu are lungimea 1, atunci vedem daca se poate obtine folosind
        {                                           //o perla de tipul B sau una de tipul C
           fout<<"1\n";    
        }
        else //Daca nu se poate, raspunsul este 0
        { 
           fout<<"0\n";    
        }
    }
    
    //Inchiderea fisierelor de intrare si iesire
    fin.close();
    fout.close();
    return 0;
}