#include <cstdio>

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

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    a[1]=1;
    v[0][0]=1;
    v[0][1]=0;
    for (i=1; i<=1000000; i++)
        if (a[i]==0)
    {
        v[1][0]++;
        v[1][v[1][0]]=i;
        for (j=2; j<=1000000/i; j++)
            a[i*j]++;
    }
    else if (a[i]<=7)
    {
        v[a[i]][0]++;
        v[a[i]][v[a[i]][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;
}