var
n,m,t,q,ans:longint;
f:array[1..100000]of longint;
procedure sss(a,b:longint);//pig A is in B
var i:longint;w:boolean;
begin
inc(f[b]);

if a=n then
 begin
  w:=true;
  for i:=1 to m do if f[i]=0 then begin w:=false;break;end;
  if w then inc(ans);
 end
else
 for i:=1 to m do sss(a+1,i);

dec(f[b]);
end;
begin
assign(input,'piggy.in');reset(input);
assign(output,'piggy.out');rewrite(output);
read(t);
for q:=1 to t do
 begin
  fillchar(f,sizeof(f),0);
  ans:=0;
  read(n,m);
  if n>m then begin sss(1,1);ans:=ans div(m-1);end;
  if n=m then ans:=1;
  writeln(ans);
 end;
close(input);close(output);
end.