var i,j,h,k,tal,n,m,t,v,remain:longint;
        ans:int64;
        a:array[1..50] of longint;

function com(x,y:longint):int64;
var xx,yy:int64;f,d:longint;
begin
xx:=x;
yy:=y;
f:=y;
for d:=1 to f-1 do
        begin
        dec(x);
        xx:=xx*x;
        dec(y);
        yy:=yy*y;
        end;
com:=xx div yy;
end;

begin
assign(input,'piggy.in');
reset(input);
assign(output,'piggy.out');
rewrite(output);
readln(t);
ans:=1;
for k:=1 to t do
        begin
        readln(n,m);
        if n<m then writeln('0')
                else
                begin
                if n mod m =0 then
                        begin
                        h:=n div m;
                        for i:=1 to m-1 do
                                begin
                                ans:=ans*com(n,h);
                                dec(n,h);
                                end;
                        writeln(ans);
                        end
                else
                begin
                h:=n div m;
                for i:=1 to m do
                a[i]:=h;
                remain:=n mod m;
                dec(remain);
                inc(a[m]);v:=0;
                for i:=1 to remain do
                        begin
                        inc(v);
                        inc(a[v]);
                        end;
                ans:=1;
                for i:=1 to m-1 do
                        begin
                        ans:=ans*com(n,a[i]);
                        dec(n,a[i]);
                        end;
                writeln(ans);
                end;
                end;
        end;
close(input);
close(output);
end.