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,a1,a2: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);
nmax:=500000;
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:=1 to nmax do
 writeln(fo,ndv[i],' ',i);}
for i:=1 to T do
begin
readln(fi,a1,a2);
  for j:=a1 downto 1 do
  begin
   if (j=1) and (a2<>ndv[j]) then
    begin
     writeln(fo,0);
     break;
    end;
   if a2=ndv[j] then
    begin
     writeln(fo,j);
     break;
    end;
  end;
end;
close(fo);
//readln;
end.