#include<stdio.h>
int t,N,K;
char prim[1000005], dp[1000005];
int A[8][1000005];
int main ()
{
    int i,j;
    
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);

    // preprocesare
    for (i=2;i<=1000000;i++)
        prim[i]=1;
    for(i=2;i<=1000000;i++)
        if (prim[i])
        {
            dp[i]=1;
            for(j=i+i;j<=1000000;j=j+i)
                prim[j] = 0, dp[j]++;
        }
    for(i=0;i<=7;i++)
        for (j=1;j<=1000000;j++)
            if (dp[j]==i)
                A[i][j]=j;
            else
                A[i][j]=A[i][j-1];

    for (i=1;i<=t;i++)
    {
        scanf("%d%d",&N,&K);
        printf("%d\n", A[K][N]);
    }
                
    return 0;
}