const jin=10000000000;

type arr=array[0..10]of int64;

var f:array[0..60,0..60]of arr;
    e:array[1..9]of longint;
    i,j,k,t,n,m:longint;
    a,c:arr;

function max(x,y:qword):qword;
begin if x>y then exit(x);exit(y);end;

function cheng(a:arr;b:longint):arr;
var i:longint;
begin
 fillchar(c,sizeof(c),0);
 for i:=1 to a[0]do
  begin
   c[i]:=c[i]+a[i]*b;
   c[i+1]:=c[i+1]+c[i]div jin;
   c[i]:=c[i]mod jin;
  end;
 c[0]:=a[0];
 while c[c[0]+1]>0 do inc(c[0]);
 while c[c[0]]>=jin do
  begin c[c[0]+1]:=c[c[0]]div jin;c[c[0]]:=c[c[0]]mod jin;inc(c[0]);end;
 exit(c);
end;

function jia(a,b:arr):arr;
var i:longint;
begin
 fillchar(c,sizeof(c),0);
 c[0]:=max(a[0],b[0]);
 for i:=1 to c[0]do
  begin
   c[i]:=c[i]+a[i]+b[i];
   c[i+1]:=c[i+1]+c[i]div jin;
   c[i]:=c[i]mod jin;
  end;
 if c[c[0]+1]>0 then inc(c[0]);
 exit(c);
end;

begin
 assign(input,'piggy.in');reset(input);
 assign(output,'piggy.out');rewrite(output);
 readln(t);
 e[1]:=10;for i:=2 to 9 do e[i]:=e[i-1]*10;
 for i:=1 to 60 do
  begin
   f[i,i][0]:=1;f[i,i][1]:=1;
   f[i,1][0]:=1;f[i,1][1]:=1;
  end;
 for j:=1 to 60 do
  for i:=j+1 to 60 do
   f[i,j]:=jia(cheng(f[i-1,j],j),f[i-1,j-1]);
 for k:=1 to t do
  begin
   readln(n,m);
   a:=f[n,m];
   write(a[a[0]]);
   for i:=a[0]-1 downto 1 do
    begin
     for j:=1 to 9 do if e[j]>a[i]then write('0');
     write(a[i]-1);
    end;
   writeln;
  end;
 close(output);
end.