2373: Human Gene Functions
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：1
Description
人类基因可以认为是一个基因序列，包含四种核苷酸，分别用A，C，T和G四个字母简单地表示。生物学家对鉴别人类基因并确定他们的功能很感兴趣……请你编写一个程序，按以下规则比较两个基因并确定它们的相似程度。
对于给出两个基因AGTGATG和GTTAG，测量两个基因相似度的一种方法称为对齐，在适当位置插进空格，让两个基因的长度相等，然后根据基因分值矩阵计算分数。
例如，给AGTGATG插入一个空格，就得到AGTGAT-G；给GTTAG插入三个空格，就得到-GT--TAG。把这两个字符串对齐：
AGTGAT-G
-GT--TAG
根据下列基因分值矩阵，每对匹配的字符都有相应的分值，计算的结果是：(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。
//A C G T -
int score[5][5]={{5,-1,-2,-1,-3}, //A
{-1,5,-3,-2,-4}, //C
{-2,-3,5,-2,-2}, //G
{-1,-2,-2,5,-1}, //T
{-3,-4,-2,-1,0}};//-
下面是另一种对齐方式(不同数量的空格插进不同的位置)：
AGTGATG
-GTTA-G
这种对齐方式的分值是(-3)+5+5+(-2)+5+(-1) +5=14，它比前一个要好。其实这种对齐方式是最优的。
例如，给AGTGATG插入一个空格，就得到AGTGAT-G；给GTTAG插入三个空格，就得到-GT--TAG。把这两个字符串对齐：
AGTGAT-G
-GT--TAG
根据下列基因分值矩阵，每对匹配的字符都有相应的分值，计算的结果是：(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。
//A C G T -
int score[5][5]={{5,-1,-2,-1,-3}, //A
{-1,5,-3,-2,-4}, //C
{-2,-3,5,-2,-2}, //G
{-1,-2,-2,5,-1}, //T
{-3,-4,-2,-1,0}};//-
下面是另一种对齐方式(不同数量的空格插进不同的位置)：
AGTGATG
-GTTA-G
这种对齐方式的分值是(-3)+5+5+(-2)+5+(-1) +5=14，它比前一个要好。其实这种对齐方式是最优的。
Input
输入数据有T组测试用例，在第一行给出测试用例个数T。
每个测试用例有两行，每行有一个表示基因长度的整数和一个基因序列。每个基因序列的长度大于1但是不能超过100.
每个测试用例有两行，每行有一个表示基因长度的整数和一个基因序列。每个基因序列的长度大于1但是不能超过100.
Output
输出每个测试用例的相似度，每行一个。
Sample Input Copy
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAASample Output Copy
14