#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
map<char,int> B;

char s1[105],s2[105];
int m,n;
int tu[105][105];
int biao[6][6]={{5,-1,-2,-1,-3},{-1,5,-3,-2,-4},{-2,-3,5,-2,-2},{-1,-2,-2,5,-1},{-3,-4,-2,-1,-1000}};
void chuli()
{
    B['A']=0;
    B['C']=1;
    B['G']=2;
    B['T']=3;
    B['-']=4;
    memset(tu,0,sizeof(tu));
    scanf("%d%s",&m,s1);
    scanf("%d%s",&n,s2);
    for(int i=1;i<=m;i++)
        tu[i][0]=biao[B[s1[i-1]]][4]+tu[i-1][0];
    for(int j=1;j<=n;j++)
        tu[0][j]=biao[4][B[s2[j-1]]]+tu[0][j-1];
    //daying(m,n);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int yi=tu[i-1][j-1]+biao[B[s1[i-1]]][B[s2[j-1]]];
            int er=tu[i-1][j]+biao[B[s1[i-1]]][4];
            int san=tu[i][j-1]+biao[4][B[s2[j-1]]];
            tu[i][j]=max(max(yi,er),san);
        }
    }
    printf("%d\n",tu[m][n]);
}
int main()
{
    int a;
    scanf("%d",&a);
    while(a--)
    {
        chuli();
    }
    return 0;
}