#include <cstdio>

using namespace std;

const int NMAX=1000000;
int div_pr[NMAX+1];
int sol[8][NMAX+1];

void gen_ciur_div_pr(int n)
{
    int i,d;
    for (i=2;i<=n;++i)
    {
        if (div_pr[i]==0)
        {
            for (d=i;d<=n;d+=i)
            {
                ++div_pr[d];
            }
        }
    }
}

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int t,k,i,j,n,test;
    gen_ciur_div_pr(NMAX);
    for (i=1;i<=7;++i)
    {
        for (j=1;j<=NMAX;++j)
        {
            if (div_pr[j]==i)
            {
                sol[i][j]=j;
            }
            else
            {
                sol[i][j]=sol[i][j-1];
            }
        }
    }
    scanf("%d",&t);
    for (test=1;test<=t;++test)
    {
        scanf("%d%d",&n,&k);
        if (k==0)
        {
            printf("1\n");
        }
        else
        {
            printf("%d\n",sol[k][n]);
        }
    }
    return 0;
}