1 #include <iostream>
 2 using namespace std;
 3 #define MaxSize 102
 4 char str1[MaxSize],str2[MaxSize];
 5 int dp[MaxSize][MaxSize];
 6 int cas,len1,len2;
 7 int go[5][5]={
 8     {5,-1,-2,-1,-3},
 9     {-1,5,-3,-2,-4},
10     {-2,-3,5,-2,-2},
11     {-1,-2,-2,5,-1},
12     {-3,-4,-2,-1,0}
13 };
14 
15 inline int max(int a,int b,int c){
16     a=a>c?a:c;
17     return a>b?a:b;
18 }
19 
20 inline int number(char a){
21     switch(a) {
22         case 'A':
23             return 0;
24         case 'C':
25             return 1;
26         case 'G':
27             return 2;
28         case 'T':
29             return 3;
30         default:
31             return 4;
32     }
33 }
34 int match(char *a,char *b,int &len_a,int &len_b){
35     int i,j;
36     dp[0][0]=0;
37     for(i=1;i<=len_b;i++)
38         dp[i][0]=dp[i-1][0]+go[number(a[i])][4];//状态最优解
39     for(i=1;i<=len_a;i++)
40         dp[0][i]=dp[0][i-1]+go[4][number(b[i])];
41     for(i=1;i<=len_a;i++)
42         for(j=1;j<=len_b;j++)
43             dp[i][j]=max(dp[i-1][j-1]+go[number(a[i])][number(b[j])],
44                          dp[i][j-1]+go[4][number(b[j])],
45                          dp[i-1][j]+go[number(a[i])][4]);
46     return dp[len_a][len_b];
47 }
48 int main(){
49     //freopen("in.txt","r",stdin);
50     scanf("%d",&cas);
51     while (cas--){
52         scanf("%d %s",&len1,str1+1);
53         scanf("%d %s",&len2,str2+1);
54         int ans=match(str1,str2,len1,len2);
55         printf("%d\n",ans);
56     }
57     return 0;
58 }