#include <iostream>#include <cstdio>#include <string.h>using namespace std;int value[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 main(){int ncase;scanf("%d",&ncase);int num_a;int num_b;char a;int str[108][2];int i ,k,j;int result[108][108]={0};while (ncase -- ){memset(str,0,sizeof(str));scanf("%d%*c",&num_a);k = 0;for ( i = 0 ; i < num_a;i++){scanf("%c",&a);if( a == 'A') str[i][k] = 0 ;else if( a == 'C') str[i][k]=1;else if( a=='G')str[i][k]=2;else if( a=='T')str[i][k] = 3;else str[i][k] = 4;}getchar();scanf("%d%*c",&num_b);k = 1;for ( i = 0 ; i < num_b;i++){scanf("%c",&a);if( a == 'A') str[i][k] = 0 ;else if( a == 'C') str[i][k]=1;else if( a=='G')str[i][k]=2;else if( a=='T')str[i][k] = 3;else str[i][k] = 4;}getchar();for(i = 0;i<num_a+1;i++){for(j= 0 ; j<num_b+1;j++){result[i][j] = -1000;}}result[0][0] = 0;for(i = 0 ; i < num_a;i++){for(j = 0 ; j<num_b;j++){if(i+1 <= num_a && result[i][j] + value[ str[i][0] ][ 4 ] > result[ i + 1 ][j]) result[ i + 1 ][j] = result[i][j] + value[ str[i][0] ][ 4 ];if( j+1 <= num_b && result[i][j] + value[4][ str[j][1] ] > result[i][j+1]) result[i][j+1] = result[i][j] + value[4][ str[j][1] ] ;if( j+1 <= num_b && i+1 <= num_a && result[i][j] + value[str[i][0] ] [str[j][1]] > result[i+1][j+1])result[i+1][j+1] = result[i][j] + value[str[i][0] ] [str[j][1]] ;}}printf("%dn",result[num_a][num_b]);}return 0;}
