program pascal;
var f,g:text; n,i,j,k,nr,t,mij,k0,k1,k2,k3,k4,k5,k6,k7,l:longint;
    v:array[1..1000000] of 0..1;
    x:array[1..1000000] of 0..9;
    a:array[0..7,1..1000000] of longint;
    ok:boolean;

    procedure formare;
    begin
      n:=1000000;
      for i:=2 to trunc(sqrt(n)) do
      if v[i]=0 then
        begin
        for j:=2 to (n div i) do
                begin
                v[i*j]:=1;
                inc(x[i*j]);
                end;
        end;

      x[1]:=0;
      k0:=1;
      a[0,k0]:=1;
      for i:=2 to n do
       begin
       if x[i]=0 then x[i]:=1;
       if x[i]=1 then
               begin
                inc(k1);
                a[x[i],k1]:=i;
               end
       else
       if x[i]=2 then
                begin
                 inc(k2);
                 a[x[i],k2]:=i;
                end
       else
       if x[i]=3 then
                    begin
                     inc(k3);
                     a[x[i],k3]:=i;
                    end
       else
       if x[i]=4 then
                  begin
                   inc(k4);
                   a[x[i],k4]:=i;
                  end
       else
       if x[i]=5 then
                  begin
                  inc(k5);
                  a[x[i],k5]:=i;
                  end
       else
       if x[i]=6 then
                 begin
                 inc(k6);
                 a[x[i],k6]:=i;
                 end
      else
      if x[i]=7 then
                begin
                 inc(k7);
                 a[x[i],k7]:=i;
                end;

     end;
   end;

   procedure val(s,d:longint);
   begin
   ok:=false;
   while (s<=d) and (not ok) do
    begin
    mij:=(s+d) div 2;
    if a[k,mij]=n then ok:=true
         else
         if a[k,mij]>n then d:=mij-1
                       else s:=mij+1;
    end;
   end;

begin
assign(f,'divprim.in'); reset(f);
assign(g,'divprim.out'); rewrite(g);
k0:=0; k1:=0; k2:=0; k3:=0; k4:=0; k5:=0; k6:=0; k7:=0;
formare;
readln(f,t);
for nr:=1 to t do
 begin
   readln(f,n,k);
        if k=0 then l:=k0
   else if k=1 then l:=k1
   else if k=2 then l:=k2
   else if k=3 then l:=k3
   else if k=4 then l:=k4
   else if k=5 then l:=k5
   else if k=6 then l:=k6
   else if k=7 then l:=k7;
   val(1,l);
   if ok then writeln(g,a[k,mij])
   else
   if a[k,mij]>n then
    begin
    mij:=mij-1;
    while (mij<>0) and (a[k,mij]>n) do mij:=mij-1;
    if mij=0 then writeln(g,0)
             else writeln(g,a[k,mij]);
     end
      else writeln(g,a[k,mij]);
  end;

close(f);
close(g);
end.