const maxn=3001;
var
 i,t:longint; s1,s2:ansistring;
 x,y:array[0..maxn] of char; f1,f2:array[0..maxn] of longint;
 procedure dp;
 var i,j:longint;
 begin
  for i:=1 to length(s1) do x[i]:=s1[i];
  for i:=1 to length(s2) do y[i]:=s2[i];
  for i:=1 to length(s1) do f1[i]:=1;
  x[0]:=' '; y[0]:=' '; f1[0]:=0;
  for i:=1 to length(s2) do
  begin
   for j:=0 to length(s1) do f2[j]:=maxlongint;
   for j:=i to length(s1) do
    if y[i]=x[j] then
     if f1[j-1]<>maxlongint then
      if y[i-1]=x[j-1] then
       f2[j]:=f1[j-1]
      else f2[j]:=f1[j-1]+1
     else
    else
    if f2[j-1]<>maxlongint then
     if y[i]<>x[j-1] then
      f2[j]:=f2[j-1] else f2[j]:=f2[j-1]+1;
   f1:=f2;
  end;
  if f2[length(s1)]<>maxlongint then
   writeln(f2[length(s1)]) 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(s1);
   readln(s2);
   dp;
  end;
 close(input); close(output);
end.