#include <bits/stdc++.h>
using namespace std;
int T,n,k;
#define NMAX 1000000
int D[8][NMAX+5],ciur[NMAX+5],nr[8];
int search()
{
    int i=0,step=(1<<18);
    while (step)
    {
        if (i+step<=nr[k] && D[k][i+step]<=n)
            i+=step;
        step>>=1;
    }
    return i;
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    for (int i=2;i<=NMAX;i++)
        if (!ciur[i])
            for (int j=i;j<=NMAX;j+=i)
                ciur[j]++;
    int nrDiv,poz;
    for (int i=1;i<=NMAX;i++)
    {
        nrDiv=ciur[i];
        nr[nrDiv]++;
        poz=nr[nrDiv];
        D[nrDiv][poz]=i;
    }
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d %d",&n,&k);
        poz=search();
        printf("%d\n",D[k][poz]);
    }
    return 0;
}