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

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

char g1[101],g2[101];
int best[2][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, -100
};

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)];
}

int score1(char a){
 return pscore[20+ci(a)];
}

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

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