#include <stdlib.h>
#include <stdio.h>

#if 1
#define ep printf
#else
#define ep 0 ||
#endif

char g1[101],g2[101];
int best[101][101];
int l1,l2;

char gi[]={'A','C','G','T','-'};
int pscore[]={
 5, -1, -2, -1, -3,
 -1, 5, -3, -2, -4,
 -2, -3, 5, -2, -2,
 -1, -2, -2, 5, -1,
 -3, -4, -2, -1, -100000
};

int ci(char a){
 switch(a){
  case 'A':return 0;
  case 'C':return 1;
  case 'G':return 2;
  case 'T':return 3;
  default:return 4;
 }
}

int score(char a, char b){
 return pscore[ci(a)*5+ci(b)];
}

void res(void){
 int a,b,c,d;
 scanf("%d %s\n",&l1,g1);
 scanf("%d %s\n",&l2,g2);
 best[0][0]=0;
 for(b=1;b<=l2;b++){best[0][b]=best[0][b-1]+score('-',g2[b-1]);}
 for(a=1;a<=l1;a++){
  best[a][0]=best[a-1][0]+score('-',g1[a-1]);
  for(b=1;b<=l2;b++){
   d=best[a-1][b-1]+score(g1[a-1],g2[b-1]);
   c=best[a-1][b]+score('-',g1[a-1]);
   if(d<c)d=c;
   c=best[a][b-1]+score('-',g2[a-1]);
   if(d<c)d=c;
   best[a][b]=d;
  }
 }
 printf("%d\n",best[l1][l2]);
}

int main(void){
 int i,n;
 scanf("%d\n",&n);
 for(i=0;i<n;i++){
  res();
 }
 return 0;
}