#include <iostream>
#include <fstream>
using namespace std;
int t[1000000],x[1000000];
int cautbin(long long st,long long dr,int n)
{
    long long m;
    if(st<=dr)
    {
        m=(st+dr)/2;
        if(n==x[m])return x[m];
        else if(n>x[m])
            return cautbin(m+1,dr,n);
        else return cautbin(st,m-1,n);
    }

    else
        return x[dr];

}
void zero()
{
    for(int i=0; i<1000000; i++)t[i]=0;
}
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int main()
{
    int T,n,i,j,k,p=1,m=0,v[]= {2,3,5,7,11,13,17};
    fin>>T;
    while(T>0)
    {
        T--;
        fin>>n>>k;
        if(k==0)fout<<1<<endl;
        else
        {
            for(i=0; i<k; i++)p=p*v[i];

            if(p>n) fout<<0<<endl;
            else if(p==n)fout<<n<<endl;
            else{
            for(i=0; i<k; i++)
            {
                j=p;
                while(j<=1000000)
                {
                    t[j]=1;
                    j=j*v[i];
                }
            }
            for(j=1; j<=1000000; j++)
                if(t[j]==1)
                {
                    x[m++]=j;
                }

            fout<<cautbin(1,m,n)<<endl;
            }
        }
    }


    return 0;
}