Program divizori_primi;
 var i,j,n,k,l,t,d:longint;
       fi,fo:text;
 function prim(x:longint):boolean;
 var i,j:longint;
 begin
 if x mod 2<>0 then prim:=true
               else if x=2 then prim:=true
                else prim:=false;
    i:=3;
    while i<=trunc(sqrt(x)) do
     if x mod i=0 then begin
                       i:=trunc(sqrt(x))+1;
                       prim:=false;
                       end
                  else begin
                        prim:=true;
                         i:=i+2;
                          end;
 end;
begin
 assign(fi,'divprim.in');
  reset(fi);
 assign(fo,'divprim.out');
  rewrite(fo);
 readln(fi,t);
  for i:=1 to t do begin
   read(fi,n,k);
   for l:=n downto 2 do begin
    for j:=2 to l div 2 do
     if l mod j=0 then if prim(j) then inc(d);
     if d=k then begin
                   writeln(fo,l);
                   d:=0;
                   break;
                   end
      else if (l=2) and (d<>k) then
                                    writeln(fo,'0');
     d:=0;
     end;
    end;
  close(fo);
end.