#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<=l;++i)
        for (j=p[i];j<=1000001;j+=p[i])
            dp[j]++;
        
    for (i=1;i<=1000001;++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);
        if (k==0)printf("1\n");
        else
        printf("%d\n",sol[n][k]);
        }
    return 0;
}