#include<cstdio>

#define MAXN 1000005
#define PRIME 8

int i , j , T , N , K , mark[MAXN] , A[MAXN][PRIME];

void sieve()
{
     int i , j;
     
     mark[2] = 1;
     
     for( i = 2 ; i <= MAXN / 2 ; ++i)
          mark[i * 2] = 1;
     
     for( i = 3 ; i <= MAXN ; i += 2)
          if(!mark[i])               
              for( j = 1 ; j * i  <= MAXN ; ++j)
                       mark[j * i] ++;
                       
}

void preprocesare()
{
     for ( i = 1 ; i <= MAXN ; ++i)
         for( j = 1 ; j <= 7 ; ++j) {
              A[i][j] = A[i - 1][j];
              if(mark[i] == j) A[i][j] = i;
              }


}

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    
    scanf("%d",&T);
    
    sieve() , preprocesare();
    
    for( i = 1 ; i <= T ; ++i)
    {
         scanf("%d %d",&N,&K);
         
         if(!K) printf("1\n");
         
         else  printf("%d\n",A[N][K]);
    }

return 0;
}