program divprim;
type vector1=array[0..1000001] of longint;
var t:vector1;
    n,j,x,y,i:longint;
    f1,f2:text;
procedure ciur(n:longint);
begin
i:=2;
while (i*i<=n) do begin
if t[i]=0 then begin
j:=i;
while (j<=n) do begin
t[j]:=t[j]+1;
j:=j+i;
end; end;
i:=i+1;
end;
end;
begin
assign (f1,'divprim.in');
assign (f2,'divprim.out');
reset (f1);
rewrite (f2);
readln (f1,n);
ciur(100000);
for i:=1 to n do begin
readln (f1,x,y); t[0]:=y;
for j:=x downto 0 do
if t[j]=y then begin writeln (f2,j); break; end;
end;
close (f1);
close (f2);
end.