var a:array[1..1000010] of longint;
    c,i,j,k,n:longint;
    t:array[1..7,0..1000000]of longint;

begin
assign(input,'divprim.in');reset(input);
assign(output,'divprim.out');rewrite(output);
a[1]:=0;
for i:=2 to 1000 do
  if(a[i]=0) then
    for j:=1 to 1000000 div i do a[i*j]:=i;

for i:=1001 to 1000000 do
  if a[i]=0 then a[i]:=i;

for i:=2 to 1000000 do begin
  k:=i; while k mod a[i]=0 do k:=k div a[i];
  a[i]:=1+a[k];
end;


for i:=2 to 1000000 do begin
  k:=a[i]; inc(t[k][0]); t[k][t[k][0]]:=i;
end;


readln(c);
for i:=1 to c do begin
  readln(n,k);
  if k=0 then writeln(1)
  else
  if(n<t[k][1]) then writeln(0)
  else begin
    j:=t[k][0];
    while (t[k][j]>n)and(j>0) do dec(j);
    if(j=0) then writeln(0) else writeln(t[k][j]);
  end;
end;
close(input); close(output);
end.