#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;

map<pair<char,char>,int> matrix;
string geneA, geneB;

int ma(char a, char b)
{
    return matrix[pair<char,char>(a,b)];
}

char ReA(int i)
{
	return geneA[i-1];
}

char ReB(int i)
{
	return geneB[i-1];
}

int main()
{
    matrix[pair<char,char>('A','A')]=matrix[pair<char,char>('C','C')]=
    matrix[pair<char,char>('G','G')]=matrix[pair<char,char>('T','T')]=5;
    
    matrix[pair<char,char>('A','C')]=matrix[pair<char,char>('C','A')]=-1;  
    matrix[pair<char,char>('A','G')]=matrix[pair<char,char>('G','A')]=-2;
    matrix[pair<char,char>('A','T')]=matrix[pair<char,char>('T','A')]=-1;
    matrix[pair<char,char>('A','-')]=matrix[pair<char,char>('-','A')]=-3;
    
    matrix[pair<char,char>('C','G')]=matrix[pair<char,char>('G','C')]=-3;
    matrix[pair<char,char>('C','T')]=matrix[pair<char,char>('T','C')]=-2;
    matrix[pair<char,char>('C','-')]=matrix[pair<char,char>('-','C')]=-4;
    
    matrix[pair<char,char>('G','T')]=matrix[pair<char,char>('T','G')]=-2;
    matrix[pair<char,char>('G','-')]=matrix[pair<char,char>('-','G')]=-2;
    
    matrix[pair<char,char>('T','-')]=matrix[pair<char,char>('-','T')]=-1;
    
    size_t T;
    int lenA, lenB, tem;
    vector<vector<int> > score(200,vector<int>(200,0));
    cin >> T;
    while (T--){
        cin >> lenA;
        cin >> geneA;
        cin >> lenB;
        cin >> geneB;
        score[0][0] = 0;
        tem = 0;
        for(int i = 1; i <= lenA; ++i){
            tem += ma(ReA(i), '-');
            score[i][0] = tem;
        }
        tem = 0;
        for(int i = 1; i <= lenB; ++i){
            tem += ma(ReB(i), '-');
            score[0][i] = tem;
        }
        for(int i = 1; i <= lenA; ++i){
           for(int j = 1; j <= lenB; ++j){
               score[i][j] = score[i][0] + score[0][j];
               tem = 0;
               for(int k = j; k >= 1; --k){
                   if(score[i][j] < score[i-1][k-1] + ma(ReA(i), ReB(k)) + tem)
                      score[i][j] = score[i-1][k-1] + ma(ReA(i), ReB(k)) + tem;
                   if(score[i][j] < score[i-1][k] + ma(ReA(i), '-') + tem)
                      score[i][j] = score[i-1][k] + ma(ReA(i), '-') + tem;
                   tem += ma(ReB(k), '-');
               }
               tem = 0;
               for(int k = i; k >= 1; --k){
                   if(score[i][j] < score[k-1][j-1] + ma(ReA(k), ReB(j)) + tem)
                      score[i][j] = score[k-1][j-1] + ma(ReA(k), ReB(j)) + tem;
                   if(score[i][j] < score[k][j-1] + ma('-', ReB(j)) + tem)
                      score[i][j] = score[k][j-1] + ma('-', ReB(j)) + tem;
                   tem += ma(ReA(k), '-');
               }
           }
        }
        cout<<score[lenA][lenB]<<endl;
    }
}