我们都知道人体基因是由一个序列组成，包含4个核苷酸，我们以A、C、G、T表示。魔法世界的生物学家需要确定人体基因并确定其功能，以开发新的药品抵抗天顶星人的基因武器。
人体基因的确定由计算机辅导并通过一系列生物实验，一旦基因被确定，下一步的工作即是确定其功能。
    一种方法是：通过数据库查询新的基因，这个数据存储了许多基因序列及其功能描述，当使用数据库查找时，数据库会返回相类似的基因。而生物学家假设序列相似代表功能的相似，所以，新基因可能会有的功能与相似基因的功能一样。当然，这需要一系列的实验确定。
你的职责是编制一个程序以比较两个相似的基因，如果你的程序有效，你的程序可能会作为数据库搜索功能的一部分。
例如：两个基因AGTGATG 和GTTAG，有多少相似度呢？
    我们使用插入法：例如，插入一个空档在AGTGATG中间，使之变为AGTGAT–G，再插入三个空档在GTTAG中间，使之变为–GT– –TAG，现在这两个基因长度相等。如下：
AGTGAT–G，
–GT––TAG
我们可以看到，两个基因有四处相似，即：G都在第2位，T都在第3位，T都在第6位，G都在第8位。
表是任何两个核苷酸相对应时的数字矩阵，例如A与A对应的分数为5，A与C对应的分数为-1，但要注意绝对不允许空档与空档匹配情况的出现。

则这两个基因根据该表格算出的分数为：(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。
但实际上，如果我们将这两个基因按如下方式插入空档，即：
AGTGATG
–GTTA–G
这种方式的分数为 (-3)+5+5+(-2)+5+(-1)+5=14。所以，这种插入方式要优于前面的插入方式，而实际上，这种插入方式的得分也是最高的，所以，这两个基因的相似程度应该为14。

第一行为T值，代表测试的样例数，接下来每个测试样例包括两行，每行包括一个基因长度数和该基因序列，每个基因的序列长度最小为1，最大不超过100。

　　每行包括一个数字，即每个样例的最大相似度。

2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA

14
21