#include <cstdio>
#include <cmath>
int c[1000005],sol[1000005][8];
inline void ciur(int n)
{
    int i,j;
    c[1]=1;
    for(i=2; i<=n; i+=2)
        ++c[i];
    for(i=3; i<=n; i+=2)
        if (!c[i])
            for(j=i; j<=n; j+=i)
                ++c[j];
}
inline void solutii()
{
    int i,j;
    for(i=1; i<=1000000; ++i)
        for(j=1; j<=7; ++j)
            if (c[i]!=j)
                sol[i][j]=sol[i-1][j];
            else
                sol[i][j]=i;
}
int main()
{
    ciur(1000000);
    solutii();
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int t,i,n,k;
    scanf("%d",&t);
    for(i=1; i<=t; ++i)
    {
        scanf("%d%d",&n,&k);
        printf("%d\n",sol[n][k]);
    }
    return 0;
}