Program divizori_primi;
 var i,j,n,k,l,t,s,d,m:longint;
     a:array [1..100000] of longint;
     fi,fo:text;
begin
 assign(fi,'divprim.in');
  reset(fi);
 assign(fo,'divprim.out');
  rewrite(fo);
 readln(fi,t);
   l:=6; i:=17; a[1]:=2; a[2]:=3; a[3]:=5; a[4]:=7; a[5]:=11;a[6]:=13;
 while a[l]<=100000 do begin
  repeat
   inc(j);
    if i mod a[j]=0 then m:=1;
     until (i div a[j]<=a[j]) or (m=1);
 if m=0 then begin
              inc(l);
              a[l]:=i;
              j:=0;
              end
        else begin
              m:=0;
              j:=0;
              end;
 inc(n);
 if n mod 2<>0 then
                  i:=i+2
                  else i:=i+4;
 end;
  for i:=1 to t do begin
   read(fi,n,k);  s:=0; j:=0;
      for d:=n downto a[k] do begin
        while a[j+1]<=d div 2 do begin
         if d mod a[j+1]=0 then inc(s);
         inc(j);
         end;
         if s=k then begin
                     writeln(fo,d);
                      break;
                      end
         else if d=a[k] then writeln(fo,'0');
         s:=0;
         j:=0;
          end;
          end;
 close(fo);
end.