题目描述

我们都知道人体基因是由一个序列组成,包含$\red{4}$个核苷酸,我们以$\red{A,C,G,T}$表示。魔 法世界的生物学家需要确定人体基因并确定其功能,以开发新的药品抵抗天顶星人的基因 武器。

人体基因的确定由计算机辅导并通过一系列生物实验,一旦基因被确定,下一步的工作 即是确定其功能。

一种方法是:通过数据库查询新的基因,这个数据存储了许多基因序列及其功能描述， 当使用数据库查找时.数据库会返回相类似的基因。而生物学家假设序列相似代表功能的 相似,所以,新基因可能会有的功能与相似基因的功能一样。当然,这需要$\red{-}$系列的实验确 定。你的职责是编制一个程序以比较两个相似的基因，如果你的程序有效,你的程序可能会 作为数据库搜索功能的一部分。

例如:两个基因$\red{AGTGATG}$和$\red{GTTAG,}$有多少相似度呢?

我们使用插人法:例如.插入一个空档在$\red{AGTGATG}$中间,使之变为$\red{AGTGAT-G.}$ 再插人三个空档在$\red{GTTAG}$中间,使之变为$\red{-GT--TAG,}$现在这两个基因长度相等。 如下:

$\red{AGTG AT-G.}$

$\red{- GT--TAG}$

我们可以看到，两个基因有四处相似，即: $\red{G}$都在第$\red{2}$位,$\red{T}$都在第$\red{3}$位,$\red{T}$都在第$\red{6}$ 位,$\red{G}$都在第$\red{8}$位。

表中是任何两个核苷酸相对应时的数字矩阵，例如$\red{A}$与$\red{A}$对应的分数为$\red{5，}$$\red{A}$与$\red{C}$ 对应的分数为$\red{-1,}$但要注意绝对不允许空档与空档匹配情况的出现。

	$\red{A}$	$\red{C}$	$\red{G}$	$\red{T}$	—
$\red{A}$	$\red{5}$	$\red{-}$$\red{1}$	$\red{-}$$\red{2}$	$\red{-}$$\red{1}$	$\red{-}$$\red{3}$
$\red{C}$	$\red{-}$$\red{1}$	$\red{5}$	$\red{-}$$\red{3}$	$\red{-}$$\red{2}$	$\red{-}$$\red{4}$
$\red{G}$	$\red{-}$$\red{2}$	$\red{-}$$\red{3}$	$\red{5}$		$\red{-}$$\red{2}$
$\red{T}$	$\red{-}$$\red{1}$	$\red{-}$$\red{2}$	$\red{-}$$\red{2}$	$\red{5}$	$\red{-}$$\red{1}$
—	$\red{-}$$\red{3}$	$\red{-}$$\red{4}$		$\red{-}$$\red{1}$	$\red{*}$

则这两个基因根据该表格算出的分数为: $\red{(-3)+5+5+(-2)+(-3)+5+(-3)+}$ $\red{5=9}$。

但实际上.如果我们将这两个基因按如下方式插人空档,即:

$\red{AGTGATG}$

$\red{-GTTA-G}$

这种方式的分数为$\red{(-3)+5+5+(- 2)+5+(-1)+5=14}$。所以.这种插入方式要 优于前面的插人方式,而实际上,这种插入方式的得分也是最高的,所以,这两个基因的相似 程度应该为$\red{14}$。

输入格式

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

输出格式

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

样例

输入样例

2
7 AGTGATG
5 GTTAG
7 AGCTAT
9 AGCTTTAAA

输出样例

14
21