#include <cstdio>
#define M 1000000
#define DIM 1000002
int ndp[DIM],t,i,j,u[DIM],sol[DIM][9],n,k;

using namespace std;

int preprocesare()
{   
    
    for(i=2; i<=M; ++i)
       {
             if( !u[i] )
               {
                      for(j=2*i; j<=M; j+=i)
                         {
                                ndp[j]++;
                                u[j]=1;
                         }
               }
       }
   j=1;
   for(j=1;j<=8;++j) sol[1][j]=0;   
   for(i=2; i<=M; ++i)
      { 
            for(j=1; j<=8; ++j)
            sol[i][j]=sol[i-1][j];
      sol[i][ndp[i]]=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;
}