题目描述

众所周知，人类基因可以被视为一个由四种核苷酸组成的序列，这些核苷酸简单地用四个字母 A、C、G 和 T 表示。生物学家对识别人类基因并确定其功能非常感兴趣，因为这些功能可以用于诊断人类疾病并设计新的药物。

人类基因可以通过一系列耗时的生物实验来识别，通常借助计算机程序的帮助。一旦获得基因序列，下一步就是确定其功能。

生物学家在确定新识别的基因序列的功能时，其中一种方法是使用数据库搜索，以新基因为查询。要搜索的数据库存储了许多基因序列及其功能——许多研究人员已经将他们的基因和功能提交到数据库中，该数据库可以通过互联网自由访问。

数据库搜索将返回一个基因序列列表，这些序列与查询基因相似。

生物学家假设序列相似性通常意味着功能相似性。因此，新基因的功能可能是列表中基因所具有的功能之一。要准确确定哪一个是正确的，还需要进行另一系列生物实验。

你的任务是编写一个程序，比较两个基因并确定它们的相似性，如下所述。如果你能提供一个高效的程序，你的程序可能会被用作数据库搜索的一部分。

给定两个基因 AGTGATG 和 GTTAG，它们有多相似？衡量两个基因相似性的一种方法称为“比对”。在比对中，如果需要，可以在基因的适当位置插入空格，使它们长度相等，并根据评分矩阵对结果基因进行评分。

例如，在 AGTGATG 中插入一个空格，得到 AGTGAT-G，在 GTTAG 中插入三个空格，得到 –GT--TAG。空格用减号（-）表示。这两个基因现在长度相等。这两个字符串对齐如下：

AGTGAT-G
-GT--TAG

在这个比对中，有四个匹配，分别是：第二个位置的 G，第三个位置的 T，第六个位置的 T 和第八个位置的 G。每对对齐的字符根据以下评分矩阵分配一个分数。

注意：空格与空格的匹配是不被允许的。上述比对的分数为 $(-3) + 5 + 5 + (-2) + (-3) + 5 + (-3) + 5 = 9$。

当然，还有许多其他可能的比对方式。以下是另一种（在不同位置插入不同数量的空格）：

AGTGATG
-GTTA-G

这种比对的分数为 $(-3) + 5 + 5 + (-2) + 5 + (-1) + 5 = 14$。因此，这个比对比之前的更好。实际上，这是最优的，因为没有其他比对可以得到更高的分数。因此，可以说这两个基因的相似性是 14。

输入

输入包含 $T$ 个测试用例。测试用例的数量 $T$ 在输入文件的第一行给出。每个测试用例包含两行：每行包含一个整数，表示基因的长度，随后是基因序列。每个基因序列的长度至少为 1，不超过 100。

输出

输出应逐行打印每个测试用例的相似性。

输入数据 1

2 
7 AGTGATG 
5 GTTAG 
7 AGCTATT 
9 AGCTTTAAA 

输出数据 1

14
21

来源

大田 2001