program divprim;
var st,dr,mij,x,i,j,t,k,n:longint;
    mat:array[0..7,0..380000] of longint;
    l:array[1..7] of longint;
    v:array[0..1000005] of byte;
    f,g:text;
 procedure ciur;
  begin
   for i:=2 to 1000000 do
     if (v[i]=0) then
     begin
      j:=2*i;
      while j<=1000000 do
       begin
        inc(v[j]);
        j:=j+i;
       end;
      v[i]:=1;
     end;
   for i:=2 to 1000000 do
     case v[i] of
        1: begin mat[1,l[1]]:=i;
                inc(l[1]);end;
        2: begin mat[2,l[2]]:=i;
                inc(l[2]);end;
        3: begin mat[3,l[3]]:=i;
                inc(l[3]);end;
        4: begin mat[4,l[4]]:=i;
                inc(l[4]);end;
        5: begin mat[5,l[5]]:=i;
                inc(l[5]);end;
        6: begin mat[6,l[6]]:=i;
                inc(l[6]);end;
        7: begin mat[7,l[7]]:=i;
                inc(l[7]);end;
      end;
   end;
 begin
   ciur;
   assign(f,'divprim.in');
   assign(g,'divprim.out');
   reset(f);
   rewrite(g);
   readln(f,t);
    for i:=1 to t do
     begin
        readln(f,n,k);
        if (mat[k,0]>n) then
         writeln(g,'0')
        else
         begin
          st:=0;
          dr:=l[k]-1;
          x:=0;
          while (st<=dr) do
           begin
            mij:=(st+dr) div 2;
            if ( mat[k,mij] <= n ) then begin st := mij + 1; x := mij; end
            else if (mat[k,mij]>n) then dr:=mij-1;
           end;
          if ( mat[k,x] <= n ) then writeln(g,mat[k,x])
          else writeln(g,'0');
         end;
     end;
   close(f);
   close(g);
  end.