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