type tabel=array[0..7,0..1000005] of longint;
var t:tabel;
    n,m,i,j,a,b,x,y,nr,k,p:longint;
procedure cautad;
begin
for i:=1 to 100000 do begin
nr:=0; p:=2; k:=i;
while k>1 do begin
if k mod p=0 then begin
inc(nr);
while k mod p=0 do k:=k div p end;
inc(p);
if (k<>1) and (p*p>=k) then p:=k end;
if nr<=7 then t[nr,i]:=1 end end;
begin
assign(input,'divprim.in');
assign(output,'divprim.out');
reset(input);
rewrite(output);
read(n);
cautad;
for i:=1 to n do begin
read(x,k);
dec(x);
while (x<>0) and (t[k,x]=0) do dec(x);
writeln(x) end;
close(input);
close(output); end.