#include <cstdio>
#define M 1000002

int ndp[M+3],t,i,j,u[M+3],sol[M+3][8],n,k;

using namespace std;

int preprocesare()
{   
    u[1]=1;
    for(i=2; i<=M; ++i)
       {
             if( !u[i] )
               {
                      for(j=2*i; j<=M; j+=i)
                         {
                                ndp[j]++;
                                u[j]=1;
                         }
               }
       }
   for(i=1; i<=M; ++i)
      { 
            for(j=0; j<=7; ++j)
            {
            sol[i][j]=sol[i-1][j];
            if(ndp[i]==j) sol[i][j]=i; 
            }
      }        
            
return 0;          
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d\n",&t);
    preprocesare();
    while( t-- )
         {
             scanf("%d%d\n",&n,&k);
             printf("%d\n",sol[n][k] );
         }    
return 0;
}