program p_169a;
var n,t,i,d,aux:longint;
    k,fm,j:integer;
    gasit:boolean;
begin
  assign(input,'divprim.in'); reset(input);
  assign(output,'divprim.out'); rewrite(output);
  readln(t);
  while t>0 do begin
    readln(n,k);
    gasit:=false;
    for i:=n downto 2 do begin
      d:=2; aux:=i; j:=0;
      repeat
        fm:=0;
        while aux mod d=0 do begin fm:=fm+1; aux:=aux div d; end;
        if fm<>0 then j:=j+1;
        d:=d+1;
      until aux=1;
      if j=k then begin gasit:=true; break; end;
    end;
    if gasit=true then writeln(i) else writeln('0');
    t:=t-1;
  end;
  close(input); close(output);
end.