#include <stdio.h>

#define MAX  128

char g1[MAX], g2[MAX];
int n1, n2;

int best[MAX][MAX];

char score ['Z']['Z'];

int imax (int a, int b)
{
    return (a > b) ? a : b;
}

int main (void)
{
    int tasks, i, j;
    score['A']['A'] = 5; score['A']['C'] = -1; score['A']['G'] = -2;
	    score['A']['T'] = -1; score['A']['-'] = -3;
    score['C']['A'] = -1; score['C']['C'] = 5; score['C']['G'] = -3;
	    score['C']['T'] = -2; score['C']['-'] = -4;
    score['G']['A'] = -2; score['G']['C'] = -3; score['G']['G'] = 5;
	    score['G']['T'] = -2; score['G']['-'] = -2;
    score['T']['A'] = -1; score['T']['C'] = -2; score['T']['G'] = -2;
	    score['T']['T'] = 5; score['T']['-'] = -1;
    score['-']['A'] = -3; score['-']['C'] = -4; score['-']['G'] = -2;
	    score['-']['T'] = -1;
    scanf ("%d", &tasks);
    while ( tasks-- )
    {
	scanf ("%d%s%d%s", &n1, g1, &n2, g2);
	for ( i = 0;  i <= n1;  ++i )
	    for ( j = 0;  j <= n2;  ++j )
	    {
		unsigned char c1 = '-', c2= '-';
		int bst = -0x3F000000;
		if ( i == 0 && j == 0 )  bst = 0;
		if ( i > 0 )  c1 = g1[i-1];
		if ( j > 0 )  c2 = g2[j-1];
		if ( i > 0 && j > 0 )
		    bst = imax (bst, best[i-1][j-1] + score[c1][c2]);
		if ( i > 0 )
		    bst = imax (bst, best[i-1][j] + score[c1]['-']);
		if ( j > 0 )
		    bst = imax (bst, best[i][j-1] + score['-'][c2]);
		best[i][j] = bst;
	    }
	printf ("%d\n", best[n1][n2]);
    }
    return 0;
}