#include <stdio.h>
#include <math.h>
int sol[1000001][8];
int p[100000],i,j,n,t,k,l;
int dp[1000005];
char v[1000005];
int main()
{
    freopen ("divprim.in","r",stdin);
    freopen ("divprim.out","w",stdout);
    v[2]=0;p[1]=2;l=1;
    for (i=3;i<=1000001;i+=2)
        if (!v[i]){
           for (j=3*i;j<=1000001;j+=2*i)
               v[j]=1;
           p[++l]=i;
           }
    for (i=1;i<=10;++i){
        k=(int)sqrt(i);
        for (j=1;j<=k;++j)
            if (i%p[j]==0)dp[i]++;
        if (!v[i]&&i%2)dp[i]++;
        }
    for (i=1;i<=1000005;++i){
        for (j=1;j<=8;++j)
            sol[i][j]=sol[i-1][j];
        sol[i][dp[i]]=i;
        }
    scanf("%d",&t);
    for (;t;--t){
        scanf("%d %d",&n,&k);
        printf("%d",sol[n][k]);
        }
    return 0;
}