int f[110][110];
int p[6][6]={
0,0,0,0,0,0,
0,5,-1,-2,-1,-3,
0,-1,5,-3,-2,-4,
0,-2,-3,5,-2,-2,
0,-1,-2,-2,5,-1,
0,-3,-4,-2,-1,-1000000,
};
int d[130];
void dp(int len1,const char *a,int len2,const char *b){
int i,j;
memset(f,0,sizeof(f));
for(i=1;i<=len1;i++)
f[i][0]=f[i-1][0]+p(a[i],'-');//只与空格匹配
for(i=1;i<=len2;i++)
f[0][i]=f[0][i-1]+p('-',b[i]);//只与空格匹配
for(j=1;j<=len2;j++){
f[i][j]=max(f[i-1][j]+p(a[i],'-'),f[i][j-1]+p('-',b[j]));////只与空格匹配
f[i][j]=max(f[i][j],f[i-1][j-1]+p(a[i],b[j]));//a,b匹配
}
printf("%d\n",f[len1][len2]);
}
int main(){
d['A']=1;d['C']=2;d['G']=3;d['T']=4;d['-']=5;
char a[110],b[110];
int T,n,m;
cin>>T;
while(T--){
scanf("%d%s%d%s",&n,a+1,&m,b+1);
dp(n,a,m,b);
}
return 0;
}