#include <fstream.h>
#include <iostream.h>

fstream f("perle.in",ios::in);
fstream g("perle.out",ios::out);

int t,l;
char a[10001],x[11000];
//se verifica in permanenta ce ramane.

int verifica(int n){
 int i,j,k,sv;
 for(i=1;i<=n;i++){
  switch(x[i]){
   // perla de tip a se substituie direct
   case 'a': {x[i]=a[i];break;}
   //perla de tip b se substituie cu
   case 'b': {
	      if(a[i]=='2'){//regula 2b daca pe pozitia curenta este 2
	       for(j=n+1;j>=i+2;j--) x[j]=x[j-1];
	       x[i]='2';x[i+1]='b';n=n+1;
	      }
	      if(a[i]=='1'){//regula 1a3ac daca pe pozitia curenta este 1
	       for(j=n+4;j>=i+5;j--) x[j]=x[j-4];
	       x[i]='1';x[i+1]='a';x[i+2]='3';x[i+3]='a';x[i+4]='c';n=n+4;
	      }
	      break;
	     }
   //perla de tip c se substituie cu	     
   case 'c': {
	      if(a[i]=='2') x[i]='2';//2 daca pozitia curenta este 2
	      if(a[i]=='3'){//3bc daca pozitia curenta este 3
	       for(j=n+2;j>=i+3;j--) x[j]=x[j-2];
	       x[i]='3';x[i+1]='b';x[i+2]='c';n=n+2;
	      }
	      if(a[i]=='1'){//12a daca pozitia curenta este 1
	       for(j=n+2;j>=i+3;j--) x[j]=x[j-2];
	       x[i]='1';x[i+1]='2';x[i+2]='a';n=n+2;
	      }
	      break;
	     }
  }
  if(n>l) return 0;
  if(n==l){
   sv=0;
   for(k=1;k<=l;k++) if(a[k]!=x[k]) { sv=1; break; }
   if (!sv) return 1;
  }
 }
 return 0;
}

int main(){
 int i,j,k,sv;
 f>>t;
 for(i=1;i<=t;i++){
  f>>l;
  for(j=1;j<=l;j++) f>>a[j];
  sw=0;
  x[1]='a';
  if (verifica(1)==1) { g<<1<<endl; sw=1; }
  x[1]='b';
  if (verifica(1)==1 && sw==0) { g<<1<<endl; sw=1; }
  x[1]='c';
  if (verifica(1)==1 && sw==0) { g<<1<<endl; sw=1; }
  if(sw==0) g<<0<<endl;
 }
 f.close(); g.close();
 return 0;
}