var n,d,t,i,j:longint;
    k:byte;
    v:array[1..1000000]of int64;
begin
assign(input,'divprim.in');reset(input);
assign(output,'divprim.out');rewrite(output);
readln(t);
for i:=2 to 1000000 div 2 do
  if v[i]=0 then
    for d:=2 to 1000000 div i do
      v[i*d]:=v[i*d]+1;
for i:=1 to t do begin
  readln(n,k);
  if k=1 then writeln(sqr(trunc(sqrt(n))))
  else begin
  j:=n;
  while (v[j]<>k)and(j>0) do
    j:=j-1;
  if v[j]=k then writeln(j);
  if j=0 then writeln('0');
  end;
end;
close(input);close(output);
end.