#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>

#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <memory>
#include <complex>
#include <numeric>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <locale.h>

using namespace std;

#pragma pack(4)

const int    inf = 0x7f7f7f7f;
const int    INF = 0x7fffffff;
const double  pi = acos(-1.0);
const double eps = 1e-8;

#define   at(a,i) ((a)&(1<<(i)))
#define   nt(a,i) ((a)^(1<<(i)))
#define set1(a,i) ((a)|(1<<(i)))
#define set0(a,i) ((a)&(~(1<<(i))))

#define gret(a,b) (((a)-(b))>eps)
#define less(a,b) (((b)-(a))>eps)
#define equl(a,b) (fabs((a)-(b))<eps)

#define lmax(a,b) ((a)>(b)?(a):(b))
#define lmin(a,b) ((a)<(b)?(a):(b))
#define fmax(a,b) (gret(a,b)?(a):(b))
#define fmin(a,b) (less(a,b)?(a):(b))

const int MAXV = 120;

const int val[5][5]={
    {5,-1,-2,-1,-3},
    {-1,5,-3,-2,-4},
    {-2,-3,5,-2,-2},
    {-1,-2,-2,5,-1},
    {-3,-4,-2,-1,0},
};

string a,b;
int tcase,la,lb,dp[MAXV][MAXV];

int to(char o)
{
    switch(o)
    {
        case 'A':return 0;
        case 'C':return 1;
        case 'G':return 2;
        case 'T':return 3;
        case '-':return 4;
    }
}
int getVal(char a,char b)
{
    return val[to(a)][to(b)];
}

int main()
{
	//freopen("1080.txt","r",stdin);
	cin>>tcase;while(tcase--)
	{
	    cin>>la>>a;
	    cin>>lb>>b;

	    memset(dp,0,sizeof(dp));
	    for(int i=1;la>=i;i++) dp[i][0]=dp[i-1][0]+getVal(a[i-1],'-');
	    for(int i=1;lb>=i;i++) dp[0][i]=dp[0][i-1]+getVal('-',b[i-1]);
	    for(int i=1;la>=i;i++)
	    {
	        for(int j=1;lb>=j;j++)
	        {
	            dp[i][j]=max(dp[i-1][j-1]+getVal(a[i-1],b[j-1]),
                          max(dp[i][j-1]+getVal('-',b[j-1]),dp[i-1][j]+getVal(a[i-1],'-')));
	        }
	    }
	    cout<<dp[la][lb]<<endl;
	}
	return 0;
}