#include <fstream>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int i,j,n,k,t,ciur[1000005],m[15][1000005],st;

int binar(int n,int k)
{
    int dr,st,mij,t=0;
    st=1;dr=m[k][0];
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(m[k][mij]==n)
            return m[k][mij];
        else
            if(m[k][mij]>n)
                dr=mij-1;
            else
            {
                t=m[k][mij];
                st=mij+1;
            }
    }
    return t;
}
int main()
{
    for(i=2;i<=1000000;i++)
        if(ciur[i]==0)
        {
            ciur[i]=1;
            for(j=i*2;j<=1000000;j+=i)
                ciur[j]++;
        }
    for(i=2;i<=1000000;i++)
    {
        m[ciur[i]][0]++;
        m[ciur[i]][m[ciur[i]][0]]=i;
    }
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>n>>k;
        g<<binar(n,k)<<"\n";
    }
}