{$IFDEF NORMAL}
  {$I-,Q-,R-,S-}
{$ENDIF NORMAL}
{$IFDEF DEBUG}
  {$I+,Q+,R+,S-}
{$ENDIF DEBUG}
{$IFDEF RELEASE}
  {$I-,Q-,R-,S-}
{$ENDIF RELEASE}


type  matr = array[1..1000000,1..7] of longint;
      vect = array[1..1000000] of longint;
      data=record vl,k:longint; end;
      readd = array[1..100000] of data;

var fi,fo:text;
    i,t,k,nmax,j:longint;
    ct:int64;
    m:matr;
    a:readd;
    p,pr,ndv:vect;

   procedure generare;
   var i,j,k:longint;
    begin
     ct:=1
     ;
     p[1]:=1;
     p[2]:=0;
     for i:=5 to nmax div 2+1 do
      begin
       k:=2*i;
       while k<=nmax do
        begin
         p[k]:=1;
         k:=k+i;
        end;
      end;
     for i:=1 to nmax do
      begin
       if i mod 2=0 then
        p[i]:=1;
       if i mod 3=0 then
       p[i]:=1;
       p[2]:=0;
       p[3]:=0;
       if p[i]=0 then
        begin
         pr[ct]:=i;
         inc(ct);
        end;
      end;
     dec(ct);

    end;


begin
assign(fi,'divprim.in'); reset(fi);
assign(fo,'divprim.out'); rewrite(fo);
readln(fi,T);
for i:=1 to T do
 begin
  readln(fi,a[i].vl,a[i].k);
  if nmax<a[i].vl then nmax:=a[i].vl;
 end;
generare;
for i:=1 to ct do
 begin
  k:=pr[i];
  while k<=nmax do
   begin
    inc(ndv[k]);
    inc(k,pr[i]);
   end;
 end;
for i:=2 to nmax do
  for j:=1 to 7 do
   begin
    if j=ndv[i] then m[i,j]:=i
     else m[i,j]:=m[i-1,j];
   end;
for i:=1 to T do
 writeln(fo,m[a[i].vl,a[i].k]);
close(fo);
end.