type vector=array[0..7] of longint;

function prim(a:integer):boolean;
var d:integer;
begin
  while a mod 2=0 do a:=a div 2;
  d:=3;
  while (d*d<a)and(a mod d<>0) do inc(d,2);
  prim:=d*d>a;
end;

function zii(a,k:longint):integer;
var d,i:integer;
begin
  i:=0;
  if a mod 2=0 then inc(i);
  d:=3;
  while (d<=a div 2)and(i<=k) do
  begin
    if a mod d=0 then begin if prim(d) then begin inc(i); inc(d,2);
                                            end
                                            else inc(d,2);
                      end
    else inc(d,2);
  end;
  zii:=i
end;

var k,n,t:longint;
    i,j,m,l:longint;
    v:vector;
    okl,okn:boolean;
begin
v[0]:=1;v[1]:=2;v[2]:=6;v[3]:=30;v[4]:=210;v[5]:=2310;v[6]:=30030;v[7]:=510510;
assign(input,'divprim.in');reset(input);
assign(output,'divprim.out');rewrite(output);
readln(t);
 for j:=1 to t do begin
   readln(n,k);
   okn:=false;okl:=false;
   if v[k]=n then writeln(n)
   else
   if n>v[k] then begin m:=(v[k]+n)div 2; l:=v[k]+1;
     while (not okn)and(n>=m) do
       if zii(n,k)=k then okn:=true  else dec(n);
     while (not okl)and(l<=m) do
       if zii(l,k)=k then okl:=true else inc(l);
     if okn then writeln(n)
       else if okl then writeln(l)
         else writeln(v[k]);
   end
   else writeln(0);
 end;
close(input);close(output);
end.