#include <cstdio>

int i,j,t,k,n,st,dr,poz,mij,divizori,v[10][500000],p[100000];
bool a[1000010];

int nrdivprimi(int x)
{
    int nrdiv=0,i=1;
    while (x!=1 && p[i]*p[i]<=x)
    {
        if (x%p[i]==0)
        {
            nrdiv++;
            while (x%p[i]==0)
                x=x/p[i];
        }
        i++;
    }
    if (x!=1) nrdiv++;
    return nrdiv;
}

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    a[1]=1;
    for (i=1; i*i<=1000005; i++)
        if (a[i]==0)
        for (j=i; j<=1000005/i; j++)
        a[i*j]=1;

    for (i=1; i<=1000005; i++)
        if (a[i]==0)
        p[++k]=i;

        for (i=1; i<=1000000; i++)
            if (a[i]==0)
            {
                v[1][0]++;
                v[1][v[1][0]]=i;
            }
            else
            {
                divizori=nrdivprimi(i);
                v[divizori][0]++;
                v[divizori][v[divizori][0]]=i;
            }
    scanf("%d",&t);
    for (i=1; i<=t; i++)
    {
        scanf("%d%d",&n,&k);
        st=1;
        dr=v[k][0];
        poz=0;
        while (st<=dr)
        {
            mij=(st+dr)/2;
            if (v[k][mij]==n) {poz=mij; break; }
            else if (v[k][mij]<n)
            {
                st=mij+1;
                poz=mij;
            }
            else dr=mij-1;
        }
        if (poz==0)
            printf("0\n");
        else
        printf("%d\n",v[k][poz]);
    }
    return 0;
}