记录编号	39038	评测结果	AAAAAAAAAA
题目名称	DNA重组	最终得分	100
用户昵称	isabella	是否通过	通过
代码语言	Pascal	运行时间	2.462 s
提交时间	2012-07-03 17:22:30	内存使用	68.83 MiB

var
 f,g:array[1..3000,1..3000]of longint;
 i,j,n,t,l,l1,l2,ans:longint;
 s1,s2:ansistring;

 function min(a,b:longint):longint;
 begin
  if a<b then exit(a) else exit(b);
 end;

begin
assign(input,'dna.in');reset(input);
assign(output,'dna.out');rewrite(output);
 readln(t);
 for l:=1 to t do
  begin
   readln(s1);l1:=length(s1);
   readln(s2);l2:=length(s2);
   fillchar(f,sizeof(f),$7f);
   fillchar(g,sizeof(g),$7f);
   if s1[1]=s2[1] then f[1,1]:=0;
   for i:=2 to l1 do
    if s1[i]=s2[1] then f[i,1]:=1 else g[i,1]:=min(f[i-1,1],g[i-1,1]);

   for j:=2 to l2 do
    for i:=j to l1 do
     begin
      if s1[i]=s2[j]then f[i,j]:=min(f[i-1,j-1],g[i-1,j-1]+3);
      g[i,j]:=min(f[i-1,j],g[i-1,j]);
     end;

   ans:=min(f[l1,l2],g[l1,l2]+1);
   if ans<2000000000 then writeln(ans) else writeln(-1);
  end;
 close(input); close(output);
end.