program z318;

{$APPTYPE CONSOLE}
  var a:array[0..4000,0..4000,0..100]of byte;
  t,i,ii,jj,ost:integer;
  k,j,n0,n:int64;
begin
readln(t);
a[0,0,0]:=1;a[0,0,1]:=1;
a[1,0,0]:=1;a[1,0,1]:=1;
a[1,1,0]:=1;a[1,1,1]:=1;
n0:=1;
for i:=1 to t do
begin
readln(n,k);
if n>n0 then
begin
j:=n0+1;
while j<=n do begin
a[j,0,0]:=1;a[j,0,1]:=1;
a[j,j,0]:=1;a[j,j,1]:=1;
for ii:=1 to j-1 do
    begin
    ost:=0;
    if a[j-1,ii-1,0]>a[j-1,ii,0] then  a[j,ii,0]:=a[j-1,ii-1,0]
    else a[j,ii,0]:=a[j-1,ii,0];
    for jj:=1 to a[j,ii,0] do
      begin
      a[j,ii,jj]:=(ost+a[j-1,ii-1,jj]+a[j-1,ii,jj]) mod 10;
      ost:=(ost+a[j-1,ii-1,jj]+a[j-1,ii,jj]) div 10;
      end;
        if ost>0 then begin a[j,ii,0]:=a[j,ii,0]+1; a[j,ii,a[j,ii,0]]:=ost;end;
        end;

        inc(j);
        end;

end;
for ii:=a[n,k,0] downto 1 do write(a[n,k,ii]);
writeln;
n0:=n;
end;


{for i:=1 to t do begin
for ii:=a[m[i,1],m[i,2],0] downto 1 do write(a[m[i,1],m[i,2],ii]);
writeln;
end;    }

//readln;
end.