#include<stdio.h>
#include<string.h>
#define Nmax 40005
char s[Nmax],sconst[Nmax];
inline  void copy_a(char c[],const char wcopy[],int i) 
{char aux[Nmax],aux2[Nmax];
   memset(aux,0,sizeof(aux)); memset(aux2,0,sizeof(aux2));
	strncpy(aux,c,i);
   strcpy(aux2,c+i+1);
	memset(c,0,sizeof(c));
	strcpy(c,aux); strcat(c,wcopy); strcat(c,aux2);
}
void determen(char sconst[],char s[])
{int i;
	for(i=1;i<strlen(s);++i)
	    switch(sconst[i])
	            {
	              case 'A': sconst[i]=s[i];break;
			      case 'B': {if(s[i]=='2') copy_a(sconst,"2 B",i);
						        else if(s[i]=='1')copy_a(sconst,"1 A 3 A C",i);}break;
				  case 'C': {if(s[i]=='2') sconst[i]='2';
				 		        else if(s[i]=='3') copy_a(sconst,"3 B C",i);
				   		               else if(s[i]=='1') copy_a(sconst,"1 2 A",i);}break;
                }
	   
}
inline int perle_valid(char s[],int lg)
{
	if(lg==1) return 0;
	if(lg==2||lg==4) return -1;
	if(lg==3)
		if(s[0]=='1'&&s[2]=='2') return 0;
		   else return -1;
	if(lg==5)
		if(s[0]=='1'&&s[4]=='3'&&s[6]=='2') return 0;
		   else return -1;
    if(lg==6)
	   if(s[0]=='2'&&s[2]=='1'&&s[6]=='3'&&s[10]=='2') return 0;
	      else return -1;
    if(s[0]=='1') strcpy(sconst,"1 A 3 A C");
	  else if(s[0]=='2') strcpy(sconst,"2 B");
	          else  strcpy(sconst,"3 B C");
    determen(sconst,s); 
    if(strlen(s)>strlen(sconst)) memset(sconst+strlen(sconst),' ',strlen(s)-strlen(sconst));
	if(memcmp(s,sconst,sizeof(sconst))) return -1;
    return 0;
}
int main()
  {int n,i,j,lg;
	freopen("perle.in","rt",stdin);
	freopen("perle.out","wt",stdout); scanf("%d",&n);
	for(i=1;i<=n;++i)
	   {scanf("%d ",&lg); gets(s); 
		printf("%d\n",perle_valid(s,lg)+1); memset(s,0,sizeof(s)); memset(sconst,0,sizeof(sconst));
		}
	return 0;
}