#include <cstdio>
#include <cmath>

int ciur[1000003],sol[1000006][10];

void ciurr(){
    int n,lim;
    n=1000000;
    ciur[0]=ciur[1]=0;

    for(int i=2;i<=n;i++){
        if(!ciur[i]){
            for(int j=i*2;j<=n;j+=i){
                ciur[j]++;
            }
            ciur[i]=1;
        }
    }

}

void soll(){
    for(int i=2;i<=1000000;i++){
        for(int j=0;j<=7;j++){
            sol[i][j]=sol[i-1][j];
        }
        sol[i][ciur[i]]=i;
    }
}

int main(){
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);

    ciurr();
    soll();
    int t,p,nr;
    scanf("%d",&t);

    for(;t;--t){
        scanf("%d%d",&p,&nr);

        printf("%d\n",sol[p][nr]);

    }

    return 0;
}