var n,t,k,i,aux,j,nr,l:longint;
    ok:boolean;
begin
assign(input,'divprim.in');reset(input);
assign(output,'divprim.out');rewrite(output);
readln(t);
 for i:=1 to t do begin
  read(n,k);ok:=false;
  for j:=n downto 2 do begin
   aux:=j;nr:=0;
   for l:=2 to aux div 2  do
    if aux mod l=0 then begin
     inc(nr);
     while aux mod l=0 do aux:=aux div l;
    end;
    if nr=k then begin ok:=true;writeln(j);break;end;
  end;
  if not(ok) then writeln('0');
 end;
close(input);close(output);
end.