var
 f:array[1..3001,1..3001]of longint;
 s1,s2,c:ansistring;
 i,j,m,n,l1,l2,t,p:longint;

 function min(a,b:longint):longint;
 begin if a<b then exit(a) else exit(b);end;

begin
assign(input,'dna.in');reset(input);
assign(output,'dna.out');rewrite(output);
 readln(n);
 for t:=1 to n do begin
  readln(s1);l1:=length(s1);
  readln(s2);l2:=length(s2);
  fillchar(f,sizeof(f),$7f);

  if s1[l1]=s2[l2] then
   for i:=l1 downto 1 do f[i,1]:=2;

  if s1[l1]<>s2[l2]then begin
   c:='';
   for i:=l1 downto 1 do begin
    c:=s1[i]+c;
    if s1[i]=s2[l2]then f[i,1]:=3
     else begin
      p:=pos(s2[l2],c);if p<>0 then f[i,1]:=4;
     end
   end;
  end;

  for i:=l1-1 downto 1 do
   for j:=l2-1 downto 1 do begin
    if s1[i]=s2[j] then begin
        f[i,j]:=min(f[i+1,j]+2,f[i,j+1]+2);
        f[i,j]:=min(f[i,j],f[i+1,j+1]);
       end;
    if s1[i]<>s2[j] then f[i,j]:=min(f[i+1,j]+2,f[i,j+1]+2);

   end;

   writeln(f[1,1]-2);

 end;
 close(input);close(output);
end.