var v:array[0..1000005] of longint;
    t:array[0..1000005,0..8] of longint;
    n,x,y:longint;
    i,j:longint;
procedure eratostene;
begin
for i:=2 to 1000000 do begin
if v[i]=0 then begin
j:=i;
while j<=1000000 do begin
inc(v[j]);
j:=j+i end end;
t[i,v[i]]:=i end;
for j:=1 to 7 do
for i:=1 to 1000000 do
if t[i,j]=0 then t[i,j]:=t[i-1,j] end;
begin
eratostene;
read(n);
for i:=1 to n do begin
read(x,y);
writeln(t[x,y]) end end.