#include <cstdio>
#define NMax 1000005

int v[NMax],sol[NMax][8];


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

int n,k,t,i,j;

// ciur
    for(j=2;j<=NMax;j+=2) v[j]+=1;

    for(i=3;i<=NMax;i+=2)
        if(!v[i])
            for(j=i;j<=NMax;j+=i) v[j]+=1;


// solve
for(i=1;i<=NMax;++i)
    for(j=0;j<8;++j)
        if( v[i]==j ) sol[i][j]=i;
     else sol[i][j]=sol[i-1][j];



scanf("%d",&t);

for(i=0;i<t;++i)
{   scanf("%d %d",&n,&k);
    printf("%d\n",sol[n][k]);
}

return 0;
}