program divizori;
var f,g:text;
t,n,k,nmax,i,j:longint;
a:array [1..1000001] of integer;
sol:array[1..1000001,0..7] of longint;
begin
  assign(f,'divprim.in'); assign(g,'divprim.out');
  reset(f); rewrite(g);
  read(f,t);
  nmax:=0;
  for i:=1 to t do
  begin
    read(f,n,k);
    if n>nmax then nmax:=n;
  end;
  close(f);
  i:=1; sol[1,0]:=1;
  repeat
  i:=i+1;
  if a[i]=0 then
     for j:=1 to (nmax div i) do
       a[i*j]:=a[i*j]+1;
  for j:=0 to 7 do
    sol[i,j]:=sol[i-1,j];
  if a[i]<8 then sol[i,a[i]]:=i;
  until i=nmax;
  reset(f);
  read(f,t);
  nmax:=0;
  for i:=1 to t do
  begin
    read(f,n,k);
    writeln(g,sol[n,k]);
  end;
  close(f); close(g);
end.