记录编号	39067	评测结果	AAAAAAAAAA
题目名称	DNA重组	最终得分	100
用户昵称	czp	是否通过	通过
代码语言	Pascal	运行时间	2.285 s
提交时间	2012-07-03 21:14:15	内存使用	70.39 MiB

var
 dp:array[0..1,0..3033,0..3033] of longint;
 i,j,m,n,ans,v,vv:longint;
 s1,s2:ansistring;
function min(xx,yy:longint):longint;
begin if xx>yy then exit(yy) else exit(xx);end;
begin
 assign(input,'dna.in');reset(input);
 assign(output,'dna.out');rewrite(output);
 readln(v);
 for vv:=1 to v do
 begin
 fillchar(dp,sizeof(dp),$7f div 3);
 readln(s1); n:=length(s1);
 readln(s2); m:=length(s2);
 for i:=1 to m do
 for j:=1 to n do
   begin
    if s2[i]<>s1[j] then
      dp[0,i,j]:=maxlongint div 3 else
      begin
       if (i=1)  then
        begin
         if j=1 then dp[0,i,j]:=1 else
         dp[0,i,j]:=2;
        end else dp[0,i,j]:=min(dp[0,i-1,j-1],dp[1,i-1,j-1]+3);
      end;
    dp[1,i,j]:=min(dp[0,i,j-1],dp[1,i,j-1]);
   end;
 ans:=maxlongint;
 for i:=1 to n-1 do
  if dp[0,m,i]<ans then begin ans:=dp[0,m,i];  end;
 if dp[0,m,n]-1<ans then ans:=dp[0,m,n]-1;
 if ans>1000000 then writeln(-1) else writeln(ans);
 end;
 close(input);close(output);
end.