program ex;
  var f:array[1..50,1..50,0..1000] of longint;
    n,m,i,j,k,t:longint;
    const aa=10000000;
    procedure jia(x,y:Longint);
    var i,j:longint;
     begin
      for i:=1 to f[x-1,y,0] do
       begin
       f[x,y,i]:=f[x,y,i]+f[x-1,y,i]*y;
       if f[x,y,i]>=aa then
        begin
         inc(f[x,y,i+1],f[x,y,i] div aa);
         f[x,y,i]:=f[x,y,i] mod aa;
         if i+1>f[x,y,0] then f[x,y,0]:=i+1;
        end;
       end;
       if f[x,y,0]<f[x-1,y,0] then f[x,y,0]:=f[x-1,y,0];
      for i:=1 to f[x-1,y-1,0] do
       begin
         f[x,y,i]:=f[x,y,i]+f[x-1,y-1,i];
       if f[x,y,i]>=aa then
        begin
         inc(f[x,y,i+1],f[x,y,i] div aa);
         f[x,y,i]:=f[x,y,i] mod aa;
         if i+1>f[x,y,0] then f[x,y,0]:=i+1;
        end;
       end;
        if f[x,y,0]<f[x-1,y-1,0] then f[x,y,0]:=f[x-1,y-1,0];
     end;
     begin
     assign(input,'piggy.in');
     assign(output,'piggy.out');
     reset(input);
     rewrite(output);
     read(t);
     for i:=1 to 50 do
      begin
      f[i,i,1]:=1;
      f[i,i,0]:=1;
      end;
     for i:=1 to 50 do
     begin
      f[i,1,1]:=1;
      f[i,1,0]:=1;
     end;
       for i:=2 to 50 do
         for j:=2 to i-1 do
          jia(i,j);
     for i:=1 to t do
      begin
       read(n,m);
       write(f[n,m,f[n,m,0]]);
       for j:=f[n,m,0]-1 downto 1 do
        begin
         if f[n,m,j]<1000000  then write('0');
         if f[n,m,j]<100000 then write('0');
         if f[n,m,j]<10000  then write('0');
         if f[n,m,j]<1000  then write('0');
         if f[n,m,j]<100  then write('0');
         if f[n,m,j]<10  then write('0');
         write(f[n,m,j]);
        end;
        writeln;
      end;
      close(input); close(output);
     end.