#include <stdio.h>
long v[1000001],x[1000001][8];
int main() 
{
 long i,j,n,k,teste;
 freopen("divprim.in","r", stdin);
 freopen("divprim.out","w", stdout);
 for(i=2;i<=1000000;i+=2)
       v[i]++;
 for(i=3;i<=1000000;i++)
       if(v[i]==0) 
            for(j=i;j<=1000000;j+=i)
                     v[j]++;
for(i=2;i<=1000001;i++) 
    {
     for(j=0;j<8;j++)
            x[i][j]=x[i-1][j]; 
     x[i][v[i]]=i;
    }
scanf("%ld",&teste);
for(i=1;i<=teste;i++) 
        {
         scanf("%ld%ld",&n,&k);
         printf("%ld\n",x[n][k]);
        }
return 0;
}