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

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

var k,n,t:integer;
    i,j:integer;
    v:vector;
    ok:boolean;
begin
v[1]:=1;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);
   ok:=false;
   if n>=v[k] then
     while not ok do
       if zii(n)=k then ok:=true  else dec(n);
     if n>=v[k] then writeln(n)
                else writeln(0);
 end;
close(input);close(output);
end.