#include <cstdio>
#include <iostream>
using namespace std;
const int N=1000000;
int a[8][N],d[N],nr[8];
int caut(int v[],int y,int x)
{
    int i=0,pas=1<<19;
    while(pas!=0)
    {
        if(i+pas<=y&&v[i+pas]<=x)
            i+=pas;
        pas/=2;
    }
    return i;
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int nd,i,j,k,n,t,ndiv;
    n=N;
    for(i=2;i<=n;i++)
        if(d[i]==0)
            for(j=i;j<=n;j+=i)
                d[j]++;
    for(i=1;i<=n;i++)
    {
        ndiv=d[i];
        nr[ndiv]++;
        nd=nr[ndiv];
        a[ndiv][nd]=i;
    }
    cin>>t;
    for(i=1;i<=t;i++)
    {
        cin>>n>>k;
        cout<<a[k][caut(a[k],nr[k],n)]<<"\n";
    }
    return 0;
}