> # include <stdio.h>
> # define INVALID -999999
> int len1,len2;
> char c1[101],c2[101];
> int dp[101][101][201];
> int dic[6][6]={0, 0, 0, 0, 0, 0,
>                0, 5,-1,-2,-1,-3,
>                0,-1, 5,-3,-2,-4,
>                0,-2,-3, 5,-2,-2,
>                0,-1,-2,-2, 5,-1,
>                0,-3,-4,-2,-1,INVALID};
> void change(char *a)
> {
>      switch(*a)
>      {
>         case 'A':
>              *a=1;
>              break;
>         case 'C':
>              *a=2;
>              break;
>         case 'G':
>              *a=3;
>              break;
>         case 'T':
>              *a=4;
>              break;
>         };
> }
> int max(int a,int b,int c)
> {
>     int res=-99999999;
>     if(a>res) res=a;
>     if(b>res) res=b;
>     if(c>res) res=c;
>     return res;
> }
>     
> int main()
> {
>     int testcase,testcase_count;
>     scanf("%d",&testcase);
>     for(testcase_count=1;testcase_count<=testcase;testcase_count++)
>     {
>         scanf("%d ",&len1);
>         int i,j,k;
>         for(i=1;i<=len1;i++) 
>         {
>            scanf("%c",c1+i);
>            change(c1+i);
>         }
>         scanf("%d ",&len2);
>         for(i=1;i<=len2;i++) 
>         {
>            scanf("%c",c2+i);
>            change(c2+i);
>         }
>         /*-------------dp------------------------*/
>         for(i=0;i<=len1;i++)
>           for(j=0;j<=len2;j++)
>             for(k=100-len2-1;k<=len1+100+1;k++)
>               dp[i][j][k]=INVALID;
>         dp[0][0][100]=0;
>         for(i=1;i<=len1;i++)
>         {
>           int sum=0;
>           for(j=1;j<=i;j++) sum+=dic[c1[j]][5];
>           dp[i][0][100+i]=sum;
>         }
>         for(i=1;i<=len2;i++)
>         {
>           int sum=0;
>           for(j=1;j<=i;j++) sum+=dic[c2[j]][5];
>           dp[0][i][100-i]=sum;
>         }
>         for(i=1;i<=len1;i++)
>          for(j=1;j<=len2;j++)
>           for(k=100-len2;k<=100+len1;k++)
>           {
>             dp[i][j][k]=max(dp[i-1][j-1][k]+dic[c1[i]][c2[j]],
>                             dp[i][j-1][k+1]+dic[5][c2[j]],
>                             dp[i-1][j][k-1]+dic[c1[i]][5]
>                             );
>         
>           }
>           /*------------------------end of dp------------------------*/
>           printf("%d\n",dp[len1][len2][100+len1-len2]);
>     }
>     return 0;
> }
>         
>           
>            
>         
>