#include <stdio.h>
#define MAXL 10000

char sir[MAXL];
char comb[8][6] = {{"1"}, {"2"}, {"3"}, {"2B"}, {"1A3AC"}, {"2"}, {"3BC"}, {"12A"}};
char lit[8] = {"AAABBCCC"};

int max3(int a, int b, int c){
  if(a < b) a = b;
  if(a < c) a = c;
  return a;
}

char trans(char *s, int poz, int l){
  int i, possib, j, k, dr, cpoz;
  char c[MAXL];
  for(i = 0; i < 8; i++){
    possib = 1;
    if(s[0] == lit[i]){
      j = 0;
      cpoz = poz;
      while(comb[i][j] >= '1' && comb[i][j] <= '3' && possib == 1){
        if(comb[i][j] != sir[cpoz])  possib = 0;
        j++;
        cpoz++;
      }
      k = 1;
      if(comb[i][j] == '\0'){
        while(s[k] >= '1' && s[k] <= '3' && possib == 1){
          if(s[k] != sir[cpoz])  possib = 0;
          k++;
          cpoz++;
        }
      }
      if(possib){
        dr = 0;
        for( ; comb[i][j] != '\0'; j++){
          c[dr] = comb[i][j];
          dr++;
        }
        for( ; s[k] != '\0'; k++){
          c[dr] = s[k];
          dr++;
        }
        if(dr == 0){
          if(cpoz == l)  return 1;
        }
        else  if(trans(c, cpoz, l))  return 1;
      }
    }
  }
  return 0;
}

int main(){
  FILE *in = fopen("perle.in", "r");
  FILE *out = fopen("perle.out", "w");
  int n;
  fscanf(in, "%d", &n);
  int i, j, l;
  for(i = 0; i < n; i++){
    fscanf(in, "%d ", &l);
    for(j = 0; j < l; j++){
      sir[j] = fgetc(in);

      fgetc(in);
    }
    fprintf(out, "%d\n", max3(trans("A", 0, l), trans("B", 0, l), trans("C", 0, l)));
  }
  fclose(in);
  fclose(out);
  return 0;
}