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

#define IN "perle.in"
#define OUT "perle.out"
#define DIM 11111

ifstream fin(IN);
ofstream fout(OUT);

char x[DIM];
char y[DIM];
int p,sw;
int lung;

void alg();
void afis();
void prima();
int det();

int main()
{
 int i,j;
 int nr,nrr;

 fin>>nr;
 for(i=1;i<=nr;i++)
 {
  fin>>nrr;
  lung=nrr;
  for(j=0;j<nrr;j++)
   fin>>x[j];

  p=0;
  sw=1;

  prima();
  alg();

  afis();

  memset(x,0,sizeof(x));
  memset(y,0,sizeof(y));
 }

 fin.close();
 fout.close();

return 0;
}

void alg()
{
 if(sw==-1)
 {
  sw=1;
  y[0]=x[0];
  return ;
 }
 if(sw==0)
  return ;

 p=1;
 int opt;

 while(sw)
 {
  opt=det();

  if(opt==1 || opt==2 || opt==3)
  {
   y[p]=48+opt;
   p++;
  }
  else
   if(opt==4)
   {
    y[p]='2';
    y[p+1]='B';
    p++;
   }
   else
    if(opt==5)
    {
     y[p]='1';
     y[p+1]='A';
     y[p+2]='3';
     y[p+3]='A';
     y[p+4]='C';
     p++;
    }
    else
     if(opt==6)
     {
      y[p]='2';
      p++;
     }
     else
      if(opt==7)
      {
       y[p]='3';
       y[p+1]='B';
       y[p+2]='C';
       p++;
      }
      else
       if(opt==8)
       {
	y[p]='1';
	y[p+1]='2';
	y[p+2]='A';
	p++;
       }
       else
	if(opt==-1)
	 sw=0;
	else
	 if(opt==0)
	  p++;
	 else
	  if(opt==100)
	   break;
 }/////// while
}

void afis()
{
 fout<<sw<<endl;
}

int det()
{
 if((x[p]==y[p]) && y[p]==0)
  return 100;
 else
  if(x[p]==0 && y[p]!=0)
   return -1;

 if(x[p]==y[p])
  return 0;

 if(y[p]=='A')
  return x[p]-48;

 if(y[p]=='B')
  if(x[p]=='1')
   return 5;
  else
   if(x[p]=='2')
    return 4;

 if(y[p]=='C')
  if(x[p]=='2')
   return 6;
  else
   if(x[p]=='3')
    return 7;
   else
    if(x[p]=='1')
     return 8;

return -1;
}

void prima()
{
 if(lung==1)
  sw=-1;
 else
  if(lung==2)
   sw=0;
  else
  {
   sw=0;
   y[0]=x[0];

   if(x[0]=='1')
    if(x[1]=='2' && lung==3)
    {
     sw=1;
     y[1]='2';
     y[2]='A';
    }
    else
    {
     y[1]='A';
     y[2]='3';
     y[3]='A';
     y[4]='C';
     sw=1;
    }

   if(x[0]=='2')
    y[1]='B',sw=1;

   if(x[0]=='3')
   {
    sw=1;
    y[1]='B';
    y[2]='C';
   }
  }
}