#include<iostream> #include<fstream> using namespace std; int times; char a[101],b[101]; int a_size,b_size; int result[101][101]; int table[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,10000} }; int ctoi(char x){ int res=0; switch(x){ case 'A':res=0;break; case 'C':res=1;break; case 'G':res=2;break; case 'T':res=3;break; case '-':res=4;break; } return res; } void prepare(){ memset(result,0,sizeof(result)); result[0][0]=0; for(int i=0;i<a_size;i++){ result[0][i+1]=result[0][i]+table[ctoi(a[i])][ctoi('-')]; } for(int i=0;i<b_size;i++){ result[i+1][0]=result[i][0]+table[ctoi(b[i])][ctoi('-')]; } } void doDp(){ prepare(); int x,y,z; for(int i=1;i<=b_size;i++){ for(int j=1;j<=a_size;j++){ x=result[i-1][j-1]+table[ctoi(b[i-1])][ctoi(a[j-1])]; y=result[i][j-1]+table[ctoi('-')][ctoi(a[j-1])]; z=result[i-1][j]+table[ctoi(b[i-1])][ctoi('-')]; result[i][j]=max(x,y); result[i][j]=max(result[i][j],z); } } } int main(){ //streambuf *backup; // ifstream fin; // fin.open("data.in"); // backup = cin.rdbuf(); // back up cin's streambuf // cin.rdbuf(fin.rdbuf()); // assign file's streambuf to cin cin>>times; while(times--){ cin>>a_size; cin>>a; cin>>b_size; cin>>b; doDp(); cout<<result[b_size][a_size]<<endl; } return 0; }