var t,i,max,nr,j,max2:longint;
    n,k,v,prim:array[1..1000] of word;
    f,g:text;
    ok:boolean;
begin
assign (f,'divprim.in');
assign (g,'divprim.out');
reset (f);
rewrite (g);
read (f,t);
max:=0;
for i:=1 to t do
    begin
    read (f,n[i]);
    read (f,k[i]);
    if max<n[i] then max:=n[i];
    end;
for i:=2 to max+1 do
    v[i-1]:=i;
for i:=1 to max do
    prim[i]:=0;
for i:=1 to max do
    begin
     for j:=i+1 to max do
         if (v[j] mod v[i]=0) and (prim[i]=0) then prim[j]:=prim[j]+1;
    end;
for i:=1 to t do
    begin
     max2:=0;
     for j:=1 to max do
         if (prim[j]=k[i]) and (n[i]>=v[j]) and (v[j]>max2) then max2:=v[j];
     writeln (g,max2);
    end;
close (f);
close (g);
end.