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