program divk;
const max=1000000;
 var n,k,i,j,t:longint;
     a:array [1..1000000] of boolean;
     b:array [1..1000000] 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);
 b[2]:=1; b[3]:=1;
 for i:=2 to max do
  if a[i]=false then
   for j:=2 to max div i do begin
                            a[i*j]:=true;
                            inc(b[i*j]);
                            end;
 for i:=1 to t do begin
  readln(fi,n,k);
   for j:=n downto 2 do
    if b[j]=k then begin
                    writeln(fo,j);
                    break;
                    end
    else if j=2 then writeln(fo,'0');
  end;
 close(fo);
end.