type vector=array[1..7]of longint;
const max=1000000;
var v:array[1..max]of vector;
    c,e:array[1..max] of longint;
    n,i,j,t,nd:longint;
begin
  for i:=2 to 1000 do
   if c[i]=0 then
    for j:=2 to max div i do c[i*j]:=i;
  for i:=2 to max do
    if c[i]=0 then e[i]:=1
    else begin
      j:=i; while j mod c[i]=0 do j:=j div c[i];
      e[i]:=1+e[j];
    end;
  for i:=2 to max do begin
     v[i]:=v[i-1];
     v[i][e[i]]:=i;
  end;
  assign(input,'divprim.in'); reset(input);
  assign(output,'divprim.out'); rewrite(output);
  readln(t);
  for i:=1 to t do begin
    readln(n,nd); writeln(v[n,nd]);
  end;
  close(input); close(output);
end.