program divprim;
type vector1=array[0..1000001] of longint;
     tabel=array[0..7,0..1000001] of longint;
var t:vector1; sol:tabel;
    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;
procedure finddiv;
begin
for i:=1 to 7 do
for j:=1 to 100001 do
if t[j]=i then sol[i,j]:=j else sol[i,j]:=sol[i,j-1];
end;
begin
assign (f1,'divprim.in');
assign (f2,'divprim.out');
reset (f1);
rewrite (f2);
readln (f1,n);
ciur(100000); finddiv;
for i:=1 to n do begin
readln (f1,x,y);
writeln (f2,sol[y,x]);
end;
close (f1);
close (f2);
end.