//#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 char s1[], s2[];

 int dp[][];

 int table[][] = {

      , -, -, -, -,

     -,  , -, -, -,

     -, -,  , -, -,

     -, -, -,  , -,

     -, -, -, -,

 }; 

 int max(int a, int b, int c)

 {

     return max(max(a, b), c);

 }

 int f(char c)

 {

     if(c == 'A')    return ;

     if(c == 'C')    return ;

     if(c == 'G')    return ;

     if(c == 'T')    return ;

     if(c == '-')    return ;

 }

 int Similarity(char c1, char c2)

 {    return table[f(c1)][f(c2)];    }

 int main(void)

 {

     #ifdef LOCAL

         freopen("1080in.txt", "r", stdin);

     #endif

     int T;

     scanf("%d", &T);

     while(T--)

     {

         int len1, len2, i, j;

         dp[][] = ;

         scanf("%d %s", &len1, s1+);

         scanf("%d %s", &len2, s2+);

         for(i = ; i <= len1; ++i)

             dp[i][] = dp[i-][] + Similarity(s1[i], '-');

         for(i = ; i <= len2; ++i)

             dp[][i] = dp[][i-] + Similarity(s2[i], '-');

         for(i = ; i <= len1; ++i)

             for(j = ; j <= len2; ++j)

                 dp[i][j] = max(dp[i-][j]+Similarity(s1[i], '-'),

                                 dp[i][j-]+Similarity(s2[j], '-'),

                                 dp[i-][j-]+Similarity(s1[i], s2[j]));

         printf("%d\n", dp[len1][len2]);

     }

     return ;

 }