const m=1000000;max=7;
var n,t,d:longint;
    v:array[1..m] of integer;
    a:array[1..7,0..m] of longint;
    i,j:longint;
begin
  assign(input,'divprim.in');reset(input);
  assign(output,'divprim.out');rewrite(output);
  for i:=2 to m do
    if v[i]=0 then
      for j:=1 to m div i do inc(v[i*j]);
  for i:=1 to max do
    for j:=1 to m do
      if v[j]=i then a[i,j]:=j else a[i,j]:=a[i,j-1];
  readln(t);
  for i:=1 to t do begin
    readln(n,d);
    if d>max then n:=0 else n:=a[d,n];
    writeln(n);
  end;
  close(input); close(output);
end.