DNA重组

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 dna.in 输出文件 dna.out

【问题描述

在24世纪,Z国将成为科技最发达的国家,特别是在生物工程领域,他们拥有这样的高新科技,比如使用基因剪,可以将基因链从任意一处断开,而使用基因胶,又可以将任意的基因片断粘到一个集成链上。我们知道,DNA是由一个核苷酸聚合链构成的,一共有4种类型的核苷酸,分别为"A","T","C","G"。
有一次,Z国的研究人员从一些原始的有机组织中提取出了一条DNA链,他们的任务是通过对旧的DNA进行重组,进而生成一条新的DNA链。他们投资了一个计划,用如下的方式使用基因剪和基因胶。
首先,他们将DNA链在某些连接点处断开,这样整个链就会就变成一些DNA片断,然后他们再决定是保留还是丢弃这些片断,如果保留这些片断,他们将利用基因胶把它们粘成一条新链,注意,粘的过程中不能打乱这些片断原来的顺序。在整个过程中他们不得不非常小心地确定这些片断的去留。
当然了,做这些操作是需要花费代价的,每一个“剪开”的操作代价为1,每一个“粘合”操作花费代价也为1。请你写一个程序计算:如果存在一种方式生成一个新的DNA链,那么所需操作的最小代价是多少?
请看下面的例子:
旧的DNA:A---T---A---C---C---G
剪开后: A
  T   A---C   C---G
保留:       T
          C---G
新的DNA链:  T---C---G
花费代价:4


【输入格式】


输入文件第一行有一个正整数T,表示接下来测试数据的个数。每一个测试数据包含两行,每行一个字符串,第一个字符串表示旧的DNA链,第二行为新的DNA链。每个字符串都由"A","T","C"和"G"组成,每一个字符串的长度均不超过3000。


【输出格式】


  对于每一个测试数据,输出其最小花费,如果没办法生成新的DNA链,则输出“-1”。

【样例】


dna.in
2
ATACCG
TCG
ATACCG
CTG


dna.out
4
-1