记录编号	39053	评测结果	AAAAAAAAAA
题目名称	DNA重组	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	2.347 s
提交时间	2012-07-03 18:01:36	内存使用	68.92 MiB

const maxn=3001;
var
 x,y:ansistring;
 d:array[0..maxn,0..maxn,0..1] of longint;
 i,t:longint;
 function min(x,y:longint):longint;
 begin if x>y then exit(y) else exit(x); end;
 procedure dp;
 var i,j,k:longint;
 begin
  fillchar(d,sizeof(d),$7f div 2);
  k:=d[0,0,0]; d[0,0,0]:=0;
  for i:=1 to length(x) do
   begin d[0,i,1]:=0; d[0,i,0]:=1; end;
  for i:=1 to length(y) do
   for j:=1 to length(x) do
    begin
    d[i,j,1]:=min(d[i,j-1,0],d[i,j-1,1]);
    if y[i]=x[j] then
      d[i,j,0]:=min(d[i-1,j-1,0],d[i-1,j-1,1]+3)
    end;
  if k<>min(d[length(y),length(x),0],d[length(y),length(x),1]+1) then
  writeln(min(d[length(y),length(x),0],d[length(y),length(x),1]+1)) else
  writeln(-1);
 end;
begin
 assign(input,'dna.in'); reset(input);
 assign(output,'dna.out'); rewrite(output);
 readln(t);
 for i:=1 to t do
  begin
   readln(x);
   readln(y);
   dp;
  end;
 close(input); close(output);
end.