program divk;
 var n,k,i,j,t,max:longint;
     b:array [1..1000000] of byte;
     c:array [1..100000,1..2] of longint;
     b1,b2:array [1..1 shl 15] of char;
     fi, fo:text;
begin
 assign(fi,'divprim.in');
 assign(fo,'divprim.out');
 settextbuf(fi,b1);
 settextbuf(fo,b2);
  reset(fi);
  rewrite(fo);
 readln(fi,t);
 for i:=1 to t do begin
     readln(fi,c[i,1],c[i,2]);
     if c[i,1]>max then max:=c[i,1];
     end;
 for i:=2 to max do
  if b[i]=0 then begin
  b[i]:=1;
   for j:=2 to max div i do
                  if b[i*j]<8 then inc(b[i*j]);
    end;
 for i:=1 to t do begin
  if c[i,1]=1 then writeln(fo,'0')
   else
   for j:=c[i,1] downto 2 do
    if b[j]=c[i,2] then begin
                    writeln(fo,j);
                    break;
                    end
    else if j=2 then writeln(fo,'0');
  end;
 close(fo);
end.