program divprim;
var st,dr,mij,x,i,j,t,k,n:longint;
    mat:array[0..7][0..380000] of longint;
    l:array[0..7] of longint;
    v:array[0..1000005] of byte;
 procedure ciur;
  begin
   for i:=2 to 1000000 do
     if (v[i]=0)
     begin
      j:=2*i;
      while j<=1000000 do
       begin
        inc(v[j]);
        j:=j+i;
      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)/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.