var f,g:text;
    t,n,k,k1,i,j,l,iesit:longint;

function prim(x:longint):boolean;
var i,iesit:longint;
    f:boolean;
begin
  if x<2 then
    f:=false
  else
    if x=2 then
      f:=true
    else
      begin
        iesit:=0;
        for i:=2 to trunc(sqrt(x)) do
          if x mod i=0 then
            iesit:=1;
        if iesit=0 then
          f:=true
        else
          f:=false;
      end;
  prim:=f;
end;

begin
  assign(f,'divprim.in');
  assign(g,'divprim.out');
  reset(f);
  rewrite(g);
  readln(f,t);
  for l:=1 to t do
    begin
      readln(f,n,k);
      iesit:=0;
      for i:=n downto 2 do
        begin
          k1:=0;
          for j:=2 to i div 2 do
            if (prim(j)=true) and (i mod j=0) then
              inc(k1);
          if prim(i)=true then
            inc(k1);
          if k1=k then
            begin
              iesit:=1;
              writeln(g,i);
              break;
            end;
          if iesit=1 then
            break;
        end;
      if iesit=0 then
        writeln(g,'0');
    end;
  close(f);
  close(g);
end.