var
 i,j,m,n,min,ans,tx,v,vv:longint;
 f:array[1..3000,1..3000] of longint;
 s1,s2:string;
begin
 assign(input,'dna.in');reset(input);
 assign(output,'dna.out');rewrite(output);
 readln(v);
 for vv:=1 to v do
 begin
 readln(s1);n:=length(s1);
 readln(s2);m:=length(s2);
 fillchar(f,sizeof(f),$7f div 3);
 for i:=1 to n do if s1[i]=s2[1] then
  begin
   if (i=1) or (i=n) then f[1,i]:=1 else
   f[1,i]:=2;
  end;
 for i:=2 to m do
  begin
   min:=maxlongint  div 3;
   for j:=1 to n do
    begin
    if s2[i-1]=s1[j] then
     if f[i-1,j]<min then
      min:=f[i-1,j];
    if s2[i]=s1[j] then
     begin
      if (i>1) and (j>1)  and(s2[i-1]=s1[j-1]) then
       begin
       if f[i,j]>f[i-1,j-1] then f[i,j]:=f[i-1,j-1];
       end else
       if f[i,j]>min+1 then f[i,j]:=min+1;
     end;
    end;
  end;
 ans:=maxlongint;
 for i:=1 to n-1 do
  begin
  if s1[i]=s2[m] then
  if f[m,i]<ans then  ans:=f[m,i];
  end;
  if (s1[n]=s2[m]) and (f[m,n]-1<ans) then
   begin
    ans:=f[m,n]-1;
    tx:=(ans+1) div 2+(ans+1) mod 2;
    if ans+tx>maxlongint  div 4  then  writeln(-1) else
    writeln(ans+tx);
   end else
   begin
    tx:=(ans) div 2+(ans) mod 2;
    if ans+tx>maxlongint  div 4  then  writeln(-1) else
    writeln(ans+tx);
   end;
 end;
 close(input);close(output);
end.