#include<cstdio>
#include<cmath>

using namespace std;

int u,v[1000005],d[10][1000005];

void ciur(int n) {
    int i,j;
    i=2;
    if(v[i]==0)
        for(j=i; j<=n; j=j+i)
            v[j]++;
    for(i=3; i<=n; i+=2) {
        if(v[i]==0)
            for(j=i; j<=n; j=j+i)
                v[j]++;
    }
}
int main() {
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int i,ok,j;
    ciur(1000005);
    for(i=0; i<=7; ++i) {
        for(j=0; j<=1000000; ++j) {
            if(v[j]==i)
                d[i][j]=j;
            else
                d[i][j]=d[i][j-1];
        }
    }
    int t,n,k;
    scanf("%d",&t);
    for(i=1; i<=t; ++i) {
        scanf("%d%d",&n,&k);
        printf("%d\n",d[k][n]);
    }
}