#include<cstdio>
#define MAXN 1000000
#define MAXK 8
using namespace std;
int sieve[MAXN+10],dp[MAXN+10][MAXK];
void ErathostenesSieve(){
    int i,j;
    for(i=2;i<MAXN;i+=2)
        sieve[i]=1;
    for(i=3;i<MAXN;i+=2)
        if(sieve[i]==0)
            for(j=i;j<MAXN;j+=i)
                sieve[j]++;
}
void Precompute(){
    int i,j;
    for(i=1;i<MAXN;i++)
        for(j=0;j<MAXK;j++)
            if(sieve[i]==j)
                dp[i][j]=i;
            else
                dp[i][j]=dp[i-1][j];
}
int main(){
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int tests,test,n,k;
    ErathostenesSieve();
    Precompute();
    scanf("%d",&tests);
    for(test=1;test<=tests;test++){
        scanf("%d%d",&n,&k);
        printf("%d\n",dp[n][k]);
    }
    return 0;
}