program p3;
var i,j,p,q,a,b,c,t,n,k,d,max:longint;f,g:text; ok:boolean;
   v:array[1..32000]of boolean;
   s:array[1..16000]of integer;
begin
     assign(f,'divprim.in');reset(f);
     assign(g,'divprim.out');rewrite(g);
     readln(f,t);
     for i:=1 to t do begin
     read(f,n);readln(f,k);ok:=false;q:=0;
       FOR j:=2 TO N DO
       IF not (V[j]) THEN  begin
        q:=q+1;s[q]:=j;
          FOR p:=2 TO N DIV j DO
           V[p*J]:=true;end; b:=1; d:=1; max:=0;
           for a:=b to n do begin c:=0;
             for p:=d to q do begin
             if a mod s[p]=0 then
             c:=c+1;end;
              if c=k then begin
              b:=b+1;d:=1;
              ok:=true;
               if a>max then max:=a;end;end;
              if not ok then writeln(g,'0')
                        else writeln(g,max);
              for j:=1 to q do begin
              v[j]:=false;s[j]:=0;end;end;close(f);close(g);
end.