var a:array[1..1000010] of longint;
    i,j,k,n,t:longint;

begin
assign(input,'divprim.in');reset(input);
assign(output,'divprim.out');rewrite(output);
a[1]:=0;
for i:=2 to 1000 do
  if(a[i]=0) then
    for j:=1 to 1000000 div i do begin
      a[i*j]:=i;
    end;
for i:=1001 to 1000000 do
  if a[i]=0 then a[i]:=i;
for i:=2 to 1000000 do begin
  k:=i; while k mod a[i]=0 do k:=k div a[i];
  a[i]:=1+a[k];
end;
readln(t);
for i:=1 to t do begin
  readln(n,k);
  if k=0 then writeln(1)
  else begin
    while (n>0)and(a[n]<>k) do dec(n);
    writeln(n);
  end;
end;
close(input); close(output);
end.