记录编号	39035	评测结果	AAAAAAAAAA
题目名称	DNA重组	最终得分	100
用户昵称	IMSL77	是否通过	通过
代码语言	Pascal	运行时间	1.445 s
提交时间	2012-07-03 16:56:24	内存使用	73.53 MiB

program main;
type
  integer=longint;
const
  maxn=3100;
  INF=1000000;
var
  test:integer;
  n,m:integer;
  a,b:ansistring;
  d:array[0..maxn,0..maxn,0..1] of integer;

  procedure Fopen;
  begin
    assign(input,'dna.in');
    reset(input);
    assign(output,'dna.out');
    rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input);
    close(output);
  end;

  procedure Init;
  begin
    readln(a); readln(b);
    n:=length(a);
    m:=length(b);
  end;

  function min(a,b:integer):integer;
  begin
    if a<b then exit(a) else exit(b);
  end;
  procedure Dp;
  var
    i,j:integer;
    ans:integer;
  begin
    for i:=1 to n do begin d[i,0,0]:=1; d[i,0,1]:=0; end;
    for j:=1 to m do begin d[0,j,0]:=INF; d[0,j,1]:=INF; end;
    d[0,0,0]:=0; d[0,0,1]:=0;
    for i:=1 to n do
    for j:=1 to m do
    begin
      if a[i]<>b[j] then d[i,j,0]:=INF
      else d[i,j,0]:=min(d[i-1,j-1,0],d[i-1,j-1,1]+3);
      d[i,j,1]:=min(d[i-1,j,0],d[i-1,j,1]);
    end;
    ans:=min(d[n,m,0],d[n,m,1]+1);
    if ans<INF then writeln(ans) else writeln(-1);
  end;
begin
  Fopen;
  readln(test);
  while test>0 do
  begin
    dec(test);
    Init;
    Dp;
  end;
  Fclose;
end.