const c=100000;
type vector=array [1..c] of integer;
procedure eratostene(var v:vector);
var i,j:longint;
begin
 for i:=2 to c do
  if v[i]=0 then
   for j:=2 to c div i do v[i*j]:=1;
end;

var t,n,i,j,k,nr,l:longint;
    v:vector;
begin
 assign(input,'divprim.in');reset(input);
 assign(output,'divprim.out');rewrite(output);
  eratostene(v); readln(t); v[1]:=1;
  for i:=1 to t do begin
   readln(n,k);
   for j:=n downto 0 do begin
    nr:=0;
    for l:=2 to j div 2 do
     if (v[l]=0) and (j mod l=0) then inc(nr);
    if k=nr then begin
     writeln(j); break;
    end;
   end;
   if j=0 then writeln(0);
  end;
 close(input);close(output);
end.