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

#define MAX 150

int ScoringMatrix[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
};

int SimilarityofGenes(int len0,char* gene0,int len1,char* gene1);

void main()
{
	int n,i;
	int len0,len1;
	int similarity=0;
	char gene0[MAX], gene1[MAX];

	scanf("%d",&n);

	for(i=0;i<n;i++)
	{
		scanf("%d %s",&len0,gene0);
		scanf("%d %s",&len1,gene1);

		similarity = SimilarityofGenes(len0,gene0,len1,gene1);
		printf("%d\n",similarity);
	}
}

int Convert(char gene)
{
	int result;
	switch(gene)
	{
		case 'A': result = 0;break;
		case 'C': result = 1;break;
		case 'G': result = 2;break;
		case 'T': result = 3;break;
		default: result = 4;break;
	}
	return result;
}

int Max(int a,int b,int c)
{
	int result;
	result = (a>b ? a : b);
	result = result>c ? result : c;
	return result;
}

int SimilarityofGenes(int len0,char* gene0,int len1,char* gene1)
{
	int i,j;
	char dp[MAX][MAX];

	/*This is a LCS scenario*/
	dp[0][0] = 0;
	for(i=1;i<=len0;i++)
		dp[i][0] = dp[i-1][0]+ScoringMatrix[Convert(gene0[i-1])][4];
	for(j=1;j<=len1;j++)
		dp[0][j] = dp[0][j-1]+ScoringMatrix[4][Convert(gene1[j-1])];
	for(i=1;i<=len0;i++)
		for(j=1;j<=len1;j++)
		{
			dp[i][j] = Max(dp[i-1][j-1]+ScoringMatrix[Convert(gene0[i-1])][Convert(gene1[j-1])],
				dp[i][j-1]+ScoringMatrix[4][Convert(gene1[j-1])],
					dp[i-1][j]+ScoringMatrix[Convert(gene0[i-1])][4]);
		}

	return dp[len0][len1];
}