记录编号	39047	评测结果	AAAAAAAAAA
题目名称	DNA重组	最终得分	100
用户昵称	ZhouHang	是否通过	通过
代码语言	C++	运行时间	1.750 s
提交时间	2012-07-03 17:37:37	内存使用	69.44 MiB

/**
*Prob	: dna
*Data	: 2012-7-3
*Sol	: dp
*/

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

#define MaxN 3010
#define oo 100000000

using namespace std;

int T;
string a,b;
int f[MaxN][MaxN][2];

void dp()
{	
	
	memset(f,127,sizeof(f));
	
	for (int i=0; i<a.length(); i++)
	 for (int j=0; j<=i; j++)
	 {
		if (i>0) f[i][j][1] = min(f[i-1][j][0],f[i-1][j][1]);
		
		if (a[i]!=b[j]) {
			f[i][j][0] = oo; continue; }
		if (a[i]==b[j]&&i==j&&j==0) {
			f[i][j][0] = 0; continue; }
		if (a[i]==b[j]&&i>0&&j==0) {
			f[i][j][0] = 1; continue; }
		if (j>0&&i>0)
			f[i][j][0] = min(f[i-1][j-1][0],f[i-1][j-1][1]+3);
	 }
}

int main()
{
	freopen("dna.in","r",stdin);
	freopen("dna.out","w",stdout);
	
	scanf("%d",&T);
	int ans;
	for (int i=1; i<=T; i++) {
		cin>>a; cin>>b;
		dp();
		ans = min(f[a.length()-1][b.length()-1][0],f[a.length()-1][b.length()-1][1]+1);
		if (ans>=oo) ans = -1;
		printf("%d\n",ans);
	}
	
	
	fclose(stdin); fclose(stdout);
	return 0;
}