var t,i,d,j,l,h,nr,y,m,p:longint;
    n,k,s:array[1..100] of longint;
    g,x:text;
begin
assign(g,'divprim.in');
reset(g);
read(g,t);
for i:=1 to t do begin
read(g,n[i]);
read(g,k[i]);
writeln;
end;
close(g);
for i:=1 to t do
 for j:=n[i] downto 0 do  begin
  nr:=0;
  for h:=2 to j do
  begin
   d:=0;
   if j mod h=0 then
    begin
     for  y:=1 to h do
      begin
       if h mod y=0 then d:=d+1;
      end;
      if d=2 then nr:=nr+1;
   end;
  end;
  if nr=k[i] then
   begin
    m:=m+1;
    s[m]:=j;
   break;
   end
	  else
	 if j=0 then begin m:=m+1 ; s[m]:=j; end;
end;
assign(x,'divprim.out');
rewrite(x);
for p:=1 to m do begin
write(x,s[p]);
writeln(x);
end;
close(x);
end.